부산대학교 도서관

Summary: ``We consider the following questions: (1) Can one compute satisfying assignments for satisfiable Boolean formulas in polynomial time with parallel queries to NP? (2) Is the unique optimal clique problem complete for $\roman P^{\operatorname{NP}[O(\log n)]}$? (3) Is the unique satisfiability problem NP hard? \par ``We define a framework that enables us to study the complexity of generating and checking proofs of membership. We connect the three questions above to the complexity of generating and checking proofs of membership for sets in NP and $\roman P^{\operatorname{NP}[O(\log n)]}$. We show that an affirmative answer to any of the three questions implies the existence of coNP checkable proofs for $\roman P^{\operatorname{NP}[O(\log n)]}$ that can be generated in $\operatorname{FP}^{\operatorname{NP}}_{\parallel}$. Furthermore, we construct an oracle relative to which there do not exist coNP checkable proofs for NP that are generated in $\operatorname{FP}^{\operatorname{NP}}_{\parallel}$. It follows that relative to this oracle all of the questions above are answered negatively.''