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

[My Computational Complexity Web Log] Does NP=UP?

Expand Messages
  • Lance Fortnow
    Time for another of my favorite open problems. Does NP=UP imply the polynomial-time hierarchy collapses? UP is the class of languages accepted by
    Message 1 of 1 , Dec 18, 2003
    • 0 Attachment
      Time for another of my favorite open problems.

      Does NP=UP imply the polynomial-time hierarchy collapses?

      UP is the class of languages accepted by nondeterministic polynomial-time Turing machines that have at most one accepting computation for all inputs.

      This problem has loose connections to Valiant-Vazirani but Hemaspaandra, Naik, Ogiwara and Selman have the most closely related result. Consider the following proposition.

      (*) There is a set A in NP such that for all satisfiable formula φ there is a unique satisfying assignment a of φ such that (φ,a) is in A.

      Hemaspaandra et. al. show that (*) implies the polynomial-time hierarchy collapses to the second level.

      For all we know, (*) and NP=UP are incomparable. If (*) holds for some A in P then NP=UP by just guessing a. We don't know whether NP=UP implies (*) since the accepting computations of a UP machine accepting SAT need not reveal a satisfying assignment of a formula.

      There exist an oracle relative to which UP=NP≠co-NP. An relativized world with UP=NP and Σ2p≠Π2p remains open.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 12/18/2003 08:51:59 AM

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