4
$\begingroup$

Assuming P!=NP, there is a result that there are decision problems intermediate between P and NP-complete. That is, the class NP cannot be a union of two disjoint subsets: P and NP-complete.

I could never quite understand the proof of the above result. The proof I saw in a textbook was starting with the assumption that one can enumerate all P and NP-hard problems, and then proceeding with a construction of a function that didn't fit in either. However, this construction seemed a bit fishy to me; in particular, the assumption that one can start with enumerated set of problems in a particular class, the NP.

Could you refer me to a clear self-contained proof of the statement in the 1st paragraph? More generally, what would be a good reference for proofs of such results?

$\endgroup$
4
$\begingroup$

The result you're describing is called 'Ladner's Theorem.' The Wikipedia article on 'NP-Intermediate' is probably a good place to start - you can find references to Ladner's original paper there.

There's also an extensive list of such problems on the cstheory Stackexchange.

For a couple of proofs of Ladner's Theorem, check out this note adapted from Downy & Fortnow's paper 'Uniformly Hard Languages'.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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