Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer
In this connection I can't resist linking to Ryan Williams' excellent explanation of Ladner's theorem on MO:… – Qiaochu Yuan Aug 14 '10 at 7:48
@Qiaochu: Thanks, describing it as "cut and paste" seems so boring now. :-) – ShreevatsaR Aug 14 '10 at 7:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.