부산대학교 도서관

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