It is known that there are problems in P that, provably, are not solvable in less than $O(N^k)$, for some $k$. Now consider some infinite set $K \subseteq \mathbb{R}^+_0$ such as K is unbounded from above (you can think of $K$ as being $\mathbb{N}$, for easy reasoning).

Theorem: If there exists at least one problem in P for each $k \in K$ that can't be solved in less than $O(N^k)$ steps, then $P \neq NP$.

Proof: Assume that $P = NP$, what implies that there is an algorithm that can solve some NP-complete problem in $O(N^q)$ steps, for some $q$. Since the problem is NP-complete, any NP problem can be reduced to it in $O(N^r)$ steps, for some $r$. Thus, every problem in $NP$ (so, also in $P$) can be solved in $O(N^r + N^q)$ steps. Since $K$ is unbounded from above, there are infinitely many $k \in K$ such as $O(N^k) > O(N^r + N^q)$, and so, for each of these $k$, there is at least one problem in P that can't be solved in $O(N^r + N^q)$ steps. But, since we assumed $P = NP$, every problem can be solved in $O(N^r + N^q)$. Contradiction!

So, to prove that $P \neq NP$, it suffices to find a class of hard P problems, parameterized by a number $k$ -- lets call each of them HARDP-$k$ -- that for each given $k$, it is proven that the best algorithm that solves HARDP-$k$ has time complexity of $O(N^k)$.

If such a class is too hard to define, other less straight strategies can be taken. For instance, without actually defining HARDP-$k$, it suffices to prove that there exists infinitely many problems in P with ever increasing time complexity for the best possible algorithm that solves it.

So, my questions: 1) Is my theorem correct? 2) Is it already known? 3) Is it of any relevance?


closed as unclear what you're asking by David Richerby, vonbrand, André Souza Lemos, cody, Luke Mathieson Aug 26 '15 at 5:45

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ You are claiming to have a solution for a well-known, difficult open problem. This is an extraordinary claim requiring extraordinary evidence. You have not provided such so there is not much to talk about. Even if you had, this would not be a good post for SE; it is not our goal here to make broad advances to science in a single post. See here for a related discussion. $\endgroup$ – David Richerby Aug 25 '15 at 7:35
  • $\begingroup$ It is a 10 line statement which the mistake can be easily spotted by anyone well versed in the field. And someone did quite quickly. I don't get why I shouldn't seek understanding here instead of cracking my head trying to figure out what is so wrong with the argument that people do not talk about it at all (as I have clear understating that something so simple as what I suggested, if correct and relevant, would be a broadly know theorem, probably would even be taught at computer theory courses alongside Cooks theorem). $\endgroup$ – lvella Aug 25 '15 at 18:09
  • 2
    $\begingroup$ Ivella, one possible reason is that checking your work or spotting bugs in your proof isn't really what this site is intended for. In particular, one possible concern is whether your question will be of use to others in the future -- is it likely that anyone else in the future will make this exact same mistake? See e.g. here and here for some discussion. $\endgroup$ – D.W. Aug 25 '15 at 20:46

I don't think the theorem is correct. At least, your proof is not correct. The problem is in the second sentences of your proof:

Since the problem is NP-complete, any NP problem can be reduced to it in $O(N^r)$ steps, for some $r$.

This statement is not correct. There's no guarantee there is a single $r$ that works for every NP problem. You might have a different value of $r$ for each NP problem, with no upper bound on the set of all $r$. (To give a silly example: Maybe for 3SAT $r=3$, for 4SAT $r=4$, for 5SAT $r=5$, and so on. Don't take this example too seriously; it's just to give you the idea.)


The time-hierarchy theorem shows that for each $k$ there are problems solvable in time $O(n^{k+1})$ but not in time $O(n^k)$; this problem is (roughly) the halting problem for Turing machines running in time $O(n^k)$. Hence your theorem is equivalent to the conjecture $\mathsf{P} \neq \mathsf{NP}$.


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