# 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. Nov 4, 2015 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). Nov 4, 2015 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. Nov 5, 2015 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. Nov 5, 2015 at 16:37
• Interesting to see how many ways a Perlis crypticism can be interpreted. I read it as "there's going to be an exponential algorithm that is so much smaller, easier to read, easier to understand, and whose correctness is easier to be convinced of." In this interpretation, the crucial "run" is an allusion to "someone has to write the code and get it working correctly." May 10, 2022 at 2:00

The simplex method for linear programming has worst case exponential time complexity but is widely used in practice instead of the polynomial algorithms (which do exist).

• Too bad I'm limited to one upvote per post. Nov 5, 2015 at 1:48
• Good answer to be fair, although this is mainly true because in practice it does not reach its worst case complexity. Could you think of a case where the exponential algorithm is practical up to a certain size just because the worst case) growth rate is low? Nov 5, 2015 at 13:07
• Algorithms are classified (very roughly!) by worst running time, when often the very low to practically inexistent probability of the worst case makes the average (or even realistical bad cases) much more important. E.g we use quicksort because it is blindingly fast on average, even while it's worst case is very bad (but it has vanishing probability in practice if mild precautions are taken). Nov 5, 2015 at 16:33

another big/ widespread example is Prime detection/ generation for RSA cryptography. theres a P-Time algorithm discovered early this century but it runs slow in practice so the probabilistic Miller-Rabin test is used. the algorithm runs slower the more bases are tested and could be said to run in exponential time (or at least nonpolynomial) in worst case as certainty of (non)primality is increased. a pragmatic/ P-time limit/ "compromise" is chosen in implementations so that its efficient but there is still high certainty.