If we find a problem we know for sure is in NP but not in NP-complete or P, we'll have proved P!=NP. One approach then is to identify problems in NP (but not P) we haven't been able to show to be NP-complete so far and try to prove they aren't in that set. Any examples of such problems? Preferably one problem per answer?


1 Answer 1


The language constructed in the proof of Ladner's Theorem.

See also the Wikipedia page on the NP-intermediate class, which contains a list of problems that might be in NP-intermediate.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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