The Complexity of Generating and Checking Proofs of Membership

Harry Buhrman and Thomas Thierauf

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 P^NP[log]?
  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 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.