9
$\begingroup$

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:

  1. 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.
  2. Couldn't we have an arbitrarily large polynomial expression, such that this polynomial is slower to compute than some non-polynomial?
$\endgroup$
  • $\begingroup$ That is not greater time complexity but exponential time complexity, to see the difference compare $n^2$ with $2^n$ what does their corresponding values for $n=10, 100, 1000 , \cdots$ tell you? $\endgroup$ – Arjang Oct 31 '13 at 2:56
  • $\begingroup$ Sure, but what about a polynomial expression like $n^x + n^{x-1} + \ldots + n^2 + n$? $\endgroup$ – Newb Oct 31 '13 at 2:58
  • $\begingroup$ Again there are nothing compared to exponential time, or combinatorial time, exponential time catches up very fast and grows so much faster than any polynomial anyone can make up. $\endgroup$ – Arjang Oct 31 '13 at 3:11
  • $\begingroup$ What is $x$ in that polynomial? If it depends on $n$ then that expression is not a polynomial in $n$. $\endgroup$ – Trevor Wilson Oct 31 '13 at 6:37
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "any polynomial algorithm will outperform any exponential algorithm for sufficiently large instances of the problem." That's interesting! I'd be keen to see a proof of this. $\endgroup$ – Newb Oct 31 '13 at 3:04
  • 6
    $\begingroup$ @Newb Evaluate $\lim_{n\to\infty}\frac{(1+r)^n}{n^c}$ for fixed $r,c>0$. $\endgroup$ – Carlos Eugenio Thompson Pinzón Oct 31 '13 at 3:10
  • 1
    $\begingroup$ Example of a high-degree polynomial algorithm: AKS primality test with $O(n^6)$ in its best variation. Original variation was $O(n^{7.5})$ if I recall correctly. This said, it's almost never used since probabilistic algorithms are much faster. $\endgroup$ – Bakuriu Oct 31 '13 at 7:48
  • $\begingroup$ By the way. If you consider the set of all polynomial functions, this set does not have a least upper bound. I.e. there isn't a single function that is the smallest function bigger than any polynomial, so certainly there is no "sharp divide" between polynomials and non-polynomials. $\endgroup$ – Bakuriu Oct 31 '13 at 7:54
  • $\begingroup$ @MJD Fortunately, I just found the Gary & Johnson book among my unread books! I'll start reading it. Thanks! $\endgroup$ – Newb Nov 2 '13 at 7:07
7
$\begingroup$

If you accept that exponential resource use is never tractable, the minimum requirement for bounds defining tractability is that they form a class of increasing functions that are subexponential, $f(n+1)/f(n) \to 1$.

If you accept that composition of two tractable algorithms is tractable, the bounds should also be closed under function composition $f(g(n))$ where $g(n)$ is the largest size of output that the first procedure can produce on size $n$ inputs. To relate this to composition of the resource bounds themselves, the complexity measure should be for time, or include time, so that a bound of $g(n)$ implies at most $g(n)$ bits of output. Then we simply want the bounds to be closed under function composition.

Time complexity classes satisfying these conditions include polynomial time, and quasi-polynomial time. Subexponential time, whether in the weak sense $\frac{f(n+1)}{f(n)}\to 1$ or the strong sense $O(2^{n^{o(1)}})$ or the intermediate versions described at Wikipedia, is not composition-closed.

http://en.wikipedia.org/wiki/Quasi-polynomial_time#Quasi-polynomial_time .

Related:

https://cstheory.stackexchange.com/questions/3439/why-do-we-consider-log-space-as-a-model-of-efficient-computation-instead-of-pol/

$\endgroup$
  • $\begingroup$ About points 1 and 2 in the question, there actually is a stark divide if you consider limiting behavior for large $n$. Computational complexity is asymptotic complexity for that reason. The justification is that this correlates reasonably well with practical complexity, and that it also correlates with structural properties of the computational problems, which can lead to understanding and to improvements on algorithms and related data structures. $\endgroup$ – zyx Oct 31 '13 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.