Harry Buhrman and Thomas Thierauf
Abstract:
We consider the following questions:
- Can one compute satisfying assignments for satisfiable Boolean formulas
in polynomial time with parallel queries to NP?
- Is the unique optimal clique problem (UOCLIQUE)
complete for P^NP[log]?
- Is the unique satisfiability problem (USAT) NP hard?
We define a framework that enables us to study the complexity of generating
and checking proofs of membership. We connect the above three questions to the
complexity of generating and checking proofs of membership for sets in NP
and P^NP[log].
We show that an affirmative answer to any of the three questions
implies the existence of coNP checkable proofs for P^NP[log] that
can be generated in FP_tt^NP.
Furthermore,
we construct an oracle relative to
which there do not exist coNP checkable proofs for NP that are
generated
in FP_tt^NP. It follows that relative to this oracle all of the
above questions are answered negatively.