In the 1950's, Friedberg and Muchnik independently showed that there
were sets that were computably enumerable, not computable and not
complete. Does a similar result hold for complexity theory?
Suppose P≠NP. We have problems that are in P and problems that are NP-complete and we know these sets are disjoint. Is there anything else in NP? In 1975, Ladner showed the answer is yes.
Theorem (Ladner) If P≠NP then there is a set A in NP such that A is not in P and A is not NP-complete.
Suppose P≠NP. We have problems that are in P and problems that are NP-complete and we know these sets are disjoint. Is there anything else in NP? In 1975, Ladner showed the answer is yes.
Theorem (Ladner) If P≠NP then there is a set A in NP such that A is not in P and A is not NP-complete.
No comments:
Post a Comment