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

[Computational Complexity] Relativized Collapse of P and NP

Expand Messages
  • Lance
    When we teach relativization, we often ask the class for a set A such that P A =NP A . The usual answers we get are an NP-complete A (which doesn t work unless
    Message 1 of 1 , Nov 17, 2005
    • 0 Attachment
      When we teach relativization, we often ask the class for a set A such that PA=NPA. The usual answers we get are an NP-complete A (which doesn't work unless the polynomial-time hierarchy collapses) or a PSPACE-complete A which does work:
      PSPACE ⊆ PA ⊆ NPA ⊆ NPSPACE = PSPACE
      the last equality by Savitch's theorem.

      According to Steven Rudich, a student at Carnegie-Mellon suggested using A=K, the halting problem. Does this work? This led to an interesting email discussion between Rudich, Richard Beigel, Lane Hemaspaandra and few more of us getting cc'd on the messages.

      We need to use a reasonably dense encoding of K, such as the set of Java programs with no input that halt. Then in fact PK does equal NPK, but the proof is not as obvious as one would imagine. Think about it.

      And if anyone knows the original reference to PK=NPK, let us know.

      --
      Posted by Lance to Computational Complexity at 11/17/2005 07:58:00 PM

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