**Problem Detail:**

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?

###### Asked By : lvella

#### Answered By : D.W.

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

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45535

## 0 comments:

## Post a Comment

Let us know your responses and feedback