Are we interested in working on
restricted-complexity problems? For example, solving subset-sum for
n integers with target
k requires O(2^n) for brute force, but simple dynamic programming can perform in O(n*k) in pseudopolynomial time. Then there are the more difficult solutions which can achieve values like O(sqrt(n) * k * log n) in pseudopolynomial time also. I don't think any of the more involved algorithms would be easily golfable.