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

[Computational Complexity] Favorite Theorems: NP-Incomplete Sets

Expand Messages
  • Lance
    August Edition In the 1950 s Friedberg and Muchnik independently showed there existed computably enumerable but non-computable sets that are strictly weaker
    Message 1 of 1 , Sep 12, 2005
    • 0 Attachment
      August Edition

      In the 1950's Friedberg and Muchnik independently showed there existed computably enumerable but non-computable sets that are strictly weaker than the halting problem. How about a polynomial-time version? We have some natural sets that are good candidates like Factoring and Graph Isomorphism but no proofs that these sets lie in-between P and NP. Any proof would imply P≠NP and Ladner, in a theorem that now bears his name, shows that P≠NP is the only assumption you need.

      Richard Ladner, On the Structure of Polynomial Time Reducibility, JACM 1975.

      Ladner shows that if P≠NP there exists an A such that

      • A is not in P,
      • A is in NP, and
      • A is not NP-complete.
      Here is my write-up of two proofs of this result, one due to Ladner and the other to Russell Impagliazzo. Ladner proves a more general result, given any computable sets A and B with B reduces to A but A does not reduce to BE, there is a set C such that B reduces to C and C reduces to A and A does not reduce to C and C does not reduce to B. This result holds for any reasonable notion of resource-bounded reduction, and in fact you can embed any partial order between B and A.

      Ladner's proof works by blowing holes in SAT using a clever looking-back technique to keep the set in NP. In the end it is a little unsatisfying because from the viewpoint of any fixed length, the set is either NP-complete or easy on that length. Impagliazzo's proof tries to get around this by slowing down the reduction but his proof still leaves large gaps of easily computable inputs. But until we learn how to show P≠NP we won't have any other method for proving the existence of incomplete sets.

      --
      Posted by Lance to Computational Complexity at 9/12/2005 08:18:00 PM

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