The complexity of generating and checking proofs of membership. (English) Zbl 1379.68159
Puech, Claude (ed.) et al., STACS 96. 13th annual symposium on theoretical aspects of computer science. Grenoble, France, February 22–24, 1996. Proceedings. Berlin: Springer-Verlag (ISBN 3-540-60922-9). Lecture Notes in Computer Science 1046, 75-86 (1996).
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 (UOCLIQUE) complete for \(\mathrm{P}^{\mathrm{NP}[O(\log n)]}\)?
3. 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 \(\mathrm{NP}\) and \(\mathrm{P}^{\mathrm{NP}[O(\log n)]}\). We show that an affirmative answer to any of the three questions implies the existence of coNP checkable proofs for \(\mathrm{P}^{\mathrm{NP}[O(\log n)]}\) that can be generated in \(\mathrm{FP}_{\|}^{\mathrm{NP}}\). Furthermore, we construct an oracle relative to which there do not exist \(\mathrm{coNP}\) checkable proofs for \(\mathrm{NP}\) that are generated in \(\mathrm{FP}_{\|}^{\mathrm{NP}}\). It follows that relative to this oracle all of the above questions are answered negatively.
For the entire collection see [Zbl 0885.68010].
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 (UOCLIQUE) complete for \(\mathrm{P}^{\mathrm{NP}[O(\log n)]}\)?
3. 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 \(\mathrm{NP}\) and \(\mathrm{P}^{\mathrm{NP}[O(\log n)]}\). We show that an affirmative answer to any of the three questions implies the existence of coNP checkable proofs for \(\mathrm{P}^{\mathrm{NP}[O(\log n)]}\) that can be generated in \(\mathrm{FP}_{\|}^{\mathrm{NP}}\). Furthermore, we construct an oracle relative to which there do not exist \(\mathrm{coNP}\) checkable proofs for \(\mathrm{NP}\) that are generated in \(\mathrm{FP}_{\|}^{\mathrm{NP}}\). It follows that relative to this oracle all of the above questions are answered negatively.
For the entire collection see [Zbl 0885.68010].
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
