*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
Σ_{2}^{p}≠Π_{2}^{p}
remains open.

There is a relativized world in which UP^A\neq NP^A=PSPACE^A. Is there any having UP^A=coUP^A\neq ZPP^A=NP^A=PSPACE^A? Why is it difficult to place ZPP in UP though there is no derandomization barrier known unlike placing BPP in NP?

ReplyDeleteSorry I am a little confused. UP=NP would it not imply UPH=PH and UAP=PSPACE?

ReplyDeleteSorry I am a little confused. UP=NP would it not imply UPH=PH and UAP=PSPACE=SPP? So P\neq UP=NP\neq UPH=PH\neq SPP=CH=PSPACE the remaining possibility?

ReplyDeleteValiant-Vazirani gives NP in BPP^ParityP and BPP^PromiseUP.

ReplyDeleteTo get deterministic isolation it is a profoundly difficult problem.

Assume the problem has exponentially many witnesses (we can always construct by closure properties of #P). Would an odd number of witness isolation be any easier so it is possible we get NP in ParityP without NP in P^PromiseUP? Or is the question meaningless without a deep resolution of a particular difficulty?