Practical exponential time algorithms for polynomial-time solvable problems

Question

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?

• Raphael: 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: 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).
• Rick Decker: 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.
• vonbrand: 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.
• Ron Burk: 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."

Answer 1

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).

• Rick Decker: Too bad I'm limited to one upvote per post.
• Thomas Bosman: 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?
• vonbrand: 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).

Answer 2

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.

see also

• How are primes generated for RSA? and How can I generate large prime numbers for RSA? / crypto.SE

• Raphael: This does not answer the question; it does not make much sense to bring randomized algorithms with expected polynomial running time into play here.
• vzn: reaction seems to miss the point. probabilistic tests have no expected running time in the typical sense. the question was not specifically/ technically defined as to exclude this "out-of-the-box-thinking" answer & dont think lateral thinking should be penalized here, although ofc thats often an uphill battle :(