Here's a question. Have there been any theoretical results showing that if $P \neq NP$, there must exist some problems in $NP$ which are not $NP$-complete and which are not in $P$ either? Just curious because I've never seen this question addressed.
Assuming $P \neq NP$, do we know whether there are problems which are in $NP$, not in $P$ and are not $NP$ complete?
11
$\begingroup$
computer-science
np-complete
1 Answers
12
Yes, this is known as Ladner's theorem, proved by Richard Ladner in 1975. The class of such problems are called NP-intermediate. Here's one proof that does "cut and paste" between some problem in P and some NP-complete problem, here are two, and there are others.
There are also problems that are already believed to be neither NP-complete nor in P, like integer factorisation and graph isomorphism, as well as problems known to be in NP ∩ coNP but not known to be in P.
-
1In this connection I can't resist linking to Ryan Williams' excellent explanation of Ladner's theorem on MO: http://mathoverflow.net/questions/9221/what-techniques-exist-to-show-that-a-problem-is-not-np-complete/9253#9253 – 2010-08-14
-
0@Qiaochu: Thanks, describing it as "cut and paste" seems so boring now. :-) – 2010-08-14