Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Foundations of Complexity Lesson 16: Ladner's Theorem

Expand Messages
  • Lance Fortnow
    Previous Lesson In the 1950 s, Friedberg and Muchnik independently showed that there were sets that were computably enumerable, not computable and not
    Message 1 of 1 , Mar 24, 2003
    • 0 Attachment
      Previous Lesson

      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.

      I wrote up two proofs of this result, one based on Ladner's proof and one based on a proof of Impagliazzo. The write-up is taken mostly from a paper by Rod Downey and myself.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 3/24/2003 5:26:58 PM

      Powered by Blogger Pro

    Your message has been successfully submitted and would be delivered to recipients shortly.