Assuming $P \neq NP$, I expected that $NP - P \subset NPC$, but from the diagram on Wikipedia it appears to not necessarily be true.

What is an example of a problem that is complex enough to be in $NP - P$, but doesn't allow every $NP$ problem to be reduced to it in polynomial time?

  • 2
    $\begingroup$ Are you looking for NP-intermediate (wiki)? $\endgroup$ – hengxin Jan 28 '16 at 14:04
  • $\begingroup$ @hengxin Thanks, that's what I was looking for. $\endgroup$ – Overv Jan 28 '16 at 14:41