When it comes to eliminating subexpressions, they say:
"This is to be expected; ultimately, the algorithm is a simple greedy algorithm, which often doesn’t have the best track record with this sort of optimization problem. Trying to minimize the number of floating point operations required for the polynomial calculation is also likely an NP-hard problem, so any algorithm that actually solved this problem would be even slower than the one we came up with. "
It depends on what you mean - finding syntatically common subexpressions is linear or n log n depending how you do it.
Eliminating the maximum possible existing value-equivalent subexpressions is polynomial.
Finding the smallest possible set of operations or instructions to evaluate a set of expressions is provably NP-complete.
When it comes to eliminating subexpressions, they say:
"This is to be expected; ultimately, the algorithm is a simple greedy algorithm, which often doesn’t have the best track record with this sort of optimization problem. Trying to minimize the number of floating point operations required for the polynomial calculation is also likely an NP-hard problem, so any algorithm that actually solved this problem would be even slower than the one we came up with. "
It depends on what you mean - finding syntatically common subexpressions is linear or n log n depending how you do it.
Eliminating the maximum possible existing value-equivalent subexpressions is polynomial.
Finding the smallest possible set of operations or instructions to evaluate a set of expressions is provably NP-complete.
"Claude, optimize my molecular simulation program, don't make any mistakes"