Thursday, December 18, 2003

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. A relativized world with UP=NP and Σ2p≠Π2p remains open.

No comments:

Post a Comment