Existence of NP problems with complexity intermediate between P and NP-hard
-
30-10-2019 - |
Pergunta
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?
Nenhuma solução correta