I've been reading up on $P=NP$, problem tractability, etc. Here's my question:
Why is it that we consider problems that can be solved in polynomial time – or algorithms/problem-solvers running in polynomial time – nice, tractable, solvable, etc. while considering problems with a greater time complexity to be intractable, inefficient to compute, etc.?
My thoughts are that:
- Surely it can't be the case that there is a stark divide
(solvable-unsolvable) between algorithms taking polynomial time and
algorithms taking marginally more than polynomial time. - Couldn't we have an arbitrarily large polynomial expression, such
that this polynomial is slower to compute than some non-polynomial?
Best Answer
The Garey and Johnson book (Computers and Intractibility: A Guide to the Theory of NP-Completeness, 1979) has a detailed explanation of this, early on. I can't recommend it enough.
There are several reasons why problems are considered "tractable" if they have polynomial algorithms, but the most important is this: Suppose you have a computer and with it you can feasibly calculate solutions to the Widget Problem for up to 10,000 widgets. Your customer, however, needs to solve larger instances, and if you can help them, they will pay you a lot of money. To help them do this, you will invest some of the fee in upgrading your computer to the latest model, which is twice as fast as your current computer.
If your algorithm for solving the Widget Problem is $O(n)$, the new computer will solve instances involving up to 20,000 widgets, a major improvement.
If your algorithm for solving the Widget Problem is $O(n^2)$, the new computer will make it feasible to solve instances involving up to 14,142 widgets, also a major improvement.
Even if your algorithm is $O(n^3)$, it will be feasible to solve instances involving 12,599 widgets, still a significant improvement.
But if your algorithm is $O(2^n)$, the new computer will enable you to solve instances of the Widget Problem involving up to 10,001 widgets, which is hardly an improvement at all.
That is the difference between polynomial and exponential algorithms.
You are correct that there is not exactly a stark divide between polynomial and exponential algorithms. A polynomial-time algorithm that takes $153672n^{537}$ time is probably less useful in practice than an exponential one that takes $\frac{1.00001^n}{153672}$ time. But the sorts of algorithms that actually appear in practice are not usually $O(n^{537})$; they are usually $O(n^3)$ or better. And also, regarding your question 2, any polynomial algorithm will outperform any exponential algorithm for sufficiently large instances of the problem.
But yes, there are real examples of nominally exponential-time algorithms that are efficient enough to be useful in practice. The "simplex" algorithm for integer linear programming problems is one well-known example.