[My Computational Complexity Web Log] Does NP=UP?
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