# Practical exponential time algorithms for polynomial-time solvable problems

Inspired by this quote attributed to Alan Perlis:

For every polynomial-time algorithm you have, there is an exponential algorithm that I would rather run.

How I interpret this statement is that some exponential running times should be preferred over polynomial ones for realistic problem sizes. I have never actually seen such a case though.

I wonder if there are any problems for which exponential algorithms are known that are preferable to the best polynomial ones up to a nontrivial problem sizes?

• Note that there may be other reasons besides asymptotic running time. Real running time on real inputs (average vs worst case; also, google "galactic algorithms"), implementability, memory usage, ... -- the list goes on and on. – Raphael Nov 4 '15 at 11:00
• That said, I think Alan is horribly wrong, at least in the letter. I don't think he'd solve search in sorted arrays, sorting, and a myriad other problems by anything but the standard, poly-time algorithms. He's probably talking about a specific domain, though (which you should give as context). Also, similar statements can be made inside P (cf. Quicksort vs Mergesort). – Raphael Nov 4 '15 at 11:01
• On a related note, we can use Karatsuba multiplication to form the product of two $n$-bit numbers in time $0(n^{1.58})$ rather than the $O(n^2)$ time it would take naively. You can extend this to algorithms that run in time $O(n^{1+\epsilon})$ for any $\epsilon>0$ but the actual multiplicative constant is so huge that most of these are only practical when $n$ is titanically large. – Rick Decker Nov 5 '15 at 2:02
• For smallish problems, it could very well be more practical to just check all possibilities (or using some general technique like branch and bound) instead of carefully researching (and programming, and debugging) a sophisticated "optimal" algorithm. – vonbrand Nov 5 '15 at 16:37