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?
Asked By : Michael
Answered By : rphv
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'.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/19543
0 comments:
Post a Comment
Let us know your responses and feedback