Is invoking polynomials in defining the different notions of efficient computation the real obstacle to resolve the P vs NP problem? Do we need a paradigm shift by redefining what constitute an efficient computation?


We are so far from $P \neq NP$ that the use of polynomials in running time is not the primary obstacle to lower bounds. The main obstacle is much more basic than this.

The most natural alternative to polynomials of $n$ that I have seen is quasi-linear functions of $n$, that is, functions of the form $f(n) = n (\log n)^{O(1)}$. One can define quasi-linear complexity classes that are analogues of $NP$ and $P$, i.e.

$NQL = \bigcup_{c \geq 1} NTIME[n (\log n)^c]$ and

$DQL = \bigcup_{c \geq 1} TIME[n (\log n)^c]$,

and now the question becomes whether $NQL = DQL$. (For simplicity, let's fix the model of computation to be random access machines.) We have $P \neq NP$ implies $DQL \neq NQL$, and indeed this looks like a much weaker question. For a reference, see

Ashish V. Naik, Kenneth W. Regan, D. Sivakumar: On Quasilinear-Time Complexity Theory. Theor. Comput. Sci. 148(2): 325-349 (1995)

However, the $NQL$ vs $DQL$ question is still open. We cannot even rule out a linear time algorithm for SAT. So even if we severely restrict the running time of our algorithms, we are still lost as to how to prove a nontrivial time lower bound for SAT.

  • $\begingroup$ And in fact NL versus L is open as well. $\endgroup$ Aug 24 '10 at 23:35
  • 4
    $\begingroup$ Or, in other words, it's not the "P" bit of P?=NP that is the trouble. $\endgroup$ Aug 25 '10 at 5:49

From the very beginning $P$ has drawn flak for allowing high degree polynomials to count as efficient (Edmonds essentially introduced $P$ to argue that his $O(n^4)$ matching algorithm should be considered efficient, but for computers in 1965 $O(n^4)$ was definitely not efficient), but there are very good reasons that the definition has stuck:

  1. Polynomials have nice closure properties. If $O(n)$ is efficient, and we allow an efficient algorithm to call an efficient subroutine a reasonable number of times, we are forced to conclude that $O(n^2)$ is efficient too, and iterating this reasoning leads us to conclude that $O(n^c)$ is efficient for all $c$ if we want to avoid a totally arbitrary cutoff.

  2. $P$ is robust to changes in the underlying model of computation. Complexity theory is about what problems are solvable in some reasonable model of computation. There are a huge variety of equivalent models of computation that can simulate one another in polynomial time (Turing machines, register machines, stack machines, and other stranger models) and tons of variations (how many tapes does your Turing machine have? How many states?), and we have no real reason to favor one over another. If we design an algorithm for a RAM but need to preserve our definition of efficient from model to model, then we need to allow polynomial overhead for simulation. Aliens may well have computer totally different from anything we have imagined, but their definition of $P$ would be the same.

  3. $P$ is robust to technological advancement. History has shown that computer science research that is not future-proof will quickly lose its relevance. Over time, as computing power has increased, the definition of "truly efficient" has expanded to include larger polynomials, but $P$ has remained relevant.

  4. In practice, problems requiring high degree polynomials are actually rarely an issue. Generally, the difficult step is getting from exponential time to some polynomial, and once we have an algorithm in $P$ it is relatively easy to reduce the degree to something small. There is an old joke that I have heard in several talks: "every time someone proves a problem is in $P$ Bob Tarjan makes it linear."

  • $\begingroup$ Funny anecdote, and a good list defending our old friend P. $\endgroup$ Aug 25 '10 at 0:03
  • 2
    $\begingroup$ But let's not forget the Deterministic Time Hierarchy Theorem, which implies that for any $k \ge 1$ there exist problems in P that cannot be solved in $O(n^k)$ time. In particular, I'd like to see a linear time algorithm for Gaussian elimination, or a general linear time algorithm for recognition of hereditary graph classes... $\endgroup$ Sep 2 '10 at 10:35

Polynomials are involved in the notion of efficient computation due to Cobham and Edmonds, who proposed polynomials as a robust class. (Alan Cobham, The intrinsic computational difficulty of functions, Proc. 1964 International Congress for Logic, Methodology, and Philosophy of Sciences, Y. Bar-Hellel (ed.), North Holland, 24–30, 1965; Jack Edmonds, Paths, Trees, and Flowers, Canadian Journal of Mathematics 17, 449–467, 1965.)

Around the same time, Hartmanis and Stearns proved fundamental results including the deterministic time hierarchy theorem: this shows that there are decision problems that can be solved in polynomial time, but that require the polynomial time bounds to be of arbitrarily large degree. (J. Hartmanis and R. E. Stearns, On the computational complexity of algorithms, Transactions of the AMS 117, 285–306, 1965.)

There are of course other notions of "efficient computation". Schnorr and later Gurevich/Shelah explored quasi-linear time, a robust class based on notions of realtime computing. NC for many years was regarded as capturing the notion of parallelisable computation. LOGCFL is another natural class, of languages that are logspace-reducible to languages generated by context-free grammars.

I personally tend to agree that polynomial-time computation is the wrong notion of "efficient": I don't think we really want to consider problems that provably require $O(n^{1000})$ time to decide as being efficiently computable. The Cobham-Edmonds thesis seems to be that polynomial-time is an upper bound: for truly efficient computing, we want to look for a class that is contained in P.

(I would greatly appreciate a pointer to the Cobham paper online, if anyone knows of one.)

  • $\begingroup$ Thank you for this answer. It's well thought out and very thorough. Of course, it leaves the question about P vs NP unanswered. But since the answer is easily "no" and because I'd never heard of the Cobham-Edmonds thesis I've upvoted. Cheerio! $\endgroup$ Aug 24 '10 at 22:15
  • $\begingroup$ I'm not going to step into the P vs. NP quagmire right now... $\endgroup$ Aug 24 '10 at 22:16
  • $\begingroup$ I don't blame you. :-) $\endgroup$ Aug 24 '10 at 22:20

This is an old question; I hope thread necromancy is not considered poor etiquette around here.

The previous responses have focused on justifying why P and hence NP are natural classes from a complexity-theoretic point of view: it's the transitive closure of the class of linear-time problems under various natural operations, and so on.

A completely different angle on the nature of NP comes from logic. In Fagin's paper Generalized first-order spectra and polynomial-time recognizable sets he showed that the languages in NP are exactly those that can be defined by an existential formula in second-order logic.

The connection between complexity theory and logic goes way back: Ackermann's function famously cannot be proved total in primitive-recursive arithmetic, and there is a general principle in ordinal analysis whereby the strength of a formal system is related to the growth rate of those functions it can prove total. However, Fagin's analysis is still startling. If there was ever any doubt in your mind that NP is rightfully the centerpiece of complexity theory, his paper should dispel all trace of that.

  • $\begingroup$ (Successful) necromancy is rewarded with a badge. So SE certainly seems to think it is OK. $\endgroup$ Sep 29 '10 at 13:37

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.