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.
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?