<p>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:</p>

<ol>
<li><p>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.</p></li>
<li><p>$P$ is robust to changes in the underlying model of computation.  Complexity theory is about what problems are solvable in <em>some</em> 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.</p></li>
<li><p>$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.</p></li>
<li><p>In practice, problems requiring high degree polynomials are actually rarely an issue.  Generally, the difficult step is getting from exponential time to <em>some</em> 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."</p></li>
</ol>

CC BY-SA 2.5
2010-08-25T00:03:08.010Z
Funny anecdote, and a good list defending our old friend P.
Ross Snider
CC BY-SA 2.5
2010-09-02T10:35:42.873Z
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...
András Salamon
CC BY-SA 2.5
2010-08-24T23:42:45.530Z
2010-08-24T23:42:45.530Z
Ian
<p>Polynomials are involved in the notion of efficient computation due to Cobham and Edmonds, who proposed polynomials as a robust class.  (Alan Cobham, <em>The intrinsic computational difficulty of functions</em>, Proc. 1964 International Congress for Logic, Methodology, and Philosophy of Sciences, Y. Bar-Hellel (ed.), North Holland, 24–30, 1965; Jack Edmonds, <a href="http://cms.math.ca/cjm/a145530" rel="nofollow"><em>Paths, Trees, and Flowers</em></a>, Canadian Journal of Mathematics <strong>17</strong>, 449–467, 1965.)</p>

<p>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, <a href="http://dx.doi.org/10.1090/S0002-9947-1965-0170805-7" rel="nofollow"><em>On the computational complexity of algorithms</em></a>, Transactions of the AMS <strong>117</strong>, 285–306, 1965.)</p>

<p>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.  <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aN#nc" rel="nofollow">NC</a> for many years was regarded as capturing the notion of parallelisable computation.  <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aL#logcfl" rel="nofollow">LOGCFL</a> is another natural class, of languages that are logspace-reducible to languages generated by context-free grammars.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Cobham%27s_thesis" rel="nofollow">Cobham-Edmonds thesis</a> seems to be that polynomial-time is an <em>upper bound</em>: for truly efficient computing, we want to look for a class that is contained in P.</p>

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

CC BY-SA 2.5
2010-08-24T22:15:33.270Z
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!
Ross Snider
CC BY-SA 2.5
2010-08-24T22:16:34.610Z
I'm not going to step into the P vs. NP quagmire right now...
András Salamon
CC BY-SA 2.5
2010-08-24T22:20:09.210Z
I don't blame you. :-)
Ross Snider
CC BY-SA 2.5
2010-08-24T22:02:38.140Z
2010-08-24T22:02:38.140Z
András Salamon
<p>This is an old question; I hope thread necromancy is not considered poor etiquette around here.</p>
<p>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.</p>
<p>A completely different angle on the nature of NP comes from logic. In Fagin's paper <a href="https://web.archive.org/web/20120915165333/http://www.almaden.ibm.com/cs/people/fagin/genspec.pdf" rel="nofollow noreferrer">Generalized first-order spectra and polynomial-time recognizable sets</a> he showed that the languages in NP are exactly those that can be defined by an existential formula in second-order logic.</p>
<p>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.</p>

CC BY-SA 2.5
2010-09-29T13:37:09.523Z
(Successful) necromancy is rewarded with a badge.  So SE certainly seems to think it is OK.
András Salamon
CC BY-SA 4.0
2010-09-26T11:47:20.397Z
2022-07-11T07:34:51.980Z
2022-07-11T07:34:51.980Z
Per Vognsen
<p>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. </p>

<p>The most natural alternative to polynomials of $n$ that I have seen is <em>quasi-linear functions of $n$</em>, 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.</p>

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

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

<p>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</p>

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

<p><strong>However, the $NQL$ vs $DQL$ question is still open.</strong> 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.</p>

CC BY-SA 2.5
2010-08-24T23:35:14.497Z
And in fact NL versus L is open as well.
Ross Snider
CC BY-SA 2.5
2010-08-25T05:49:20.657Z
Or, in other words, it's not the "P" bit of P?=NP that is the trouble.
Charles Stewart
CC BY-SA 2.5
2010-08-24T23:28:30.843Z
2010-08-24T23:28:30.843Z
Ryan Williams
<p>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?  </p>

<cc.complexity-theory><complexity-classes><open-problem>
Are there alternatives to using polynomials in defining the different notions of efficient computation?
Mohammad Al-Turkistany
# Are there alternatives to using polynomials in defining the different notions of efficient computation?

(Asked by: username_0 on 2010-08-24)

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?

**Tags:** cc.complexity-theory, complexity-classes, open-problem


---

## 4 answers

### Answer by username_5 on 2010-08-24. Score: 14 | Accepted answer

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.

> **Comments:**
> **username_2**: And in fact NL versus L is open as well.  
> **username_6**: Or, in other words, it's not the "P" bit of P?=NP that is the trouble.  

---

### Answer by username_1 on 2010-08-24. Score: 17

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

> **Comments:**
> **username_2**: Funny anecdote, and a good list defending our old friend P.  
> **username_3**: 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...  

---

### Answer by username_3 on 2010-08-24. Score: 12

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*](http://cms.math.ca/cjm/a145530), 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*](http://dx.doi.org/10.1090/S0002-9947-1965-0170805-7), 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](http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aN#nc) for many years was regarded as capturing the notion of parallelisable computation. [LOGCFL](http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aL#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](http://en.wikipedia.org/wiki/Cobham%27s_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.)

> **Comments:**
> **username_2**: 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!  
> **username_3**: I'm not going to step into the P vs. NP quagmire right now...  
> **username_2**: I don't blame you. :-)  

---

### Answer by username_4 on 2010-09-26. Score: 10

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](https://web.archive.org/web/20120915165333/http://www.almaden.ibm.com/cs/people/fagin/genspec.pdf) 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.

> **Comments:**
> **username_3**: (Successful) necromancy is rewarded with a badge.  So SE certainly seems to think it is OK.  

---

