Inverse NP Problems

Abstract One characterization of the class NP is as the class of all languages for which there exists a polynomial-time verifier with the following properties: for every member of the language, there exists a polynomially-sized proof causing the verifier to accept; and, for every non-member, there is no proof causing the verifier to accept. Relative to a particular verifier, every member x of the language induces a set of proofs, namely, the set of proofs causing the verifier to accept x. This paper studies the complexity of deciding, given a set Π of proofs, whether or not there exists some x inducing Π (relative to a particular verifier). We call this decision problem the inverse problem for the verifier. We introduce a new notion of reduction suited for inverse problems, and use it to classify as coNP-complete the inverse problems for the “natural” verifiers of many NP-complete problems.

Authors

• Hubie Chen

Keywords

No keywords are indexed for this paper.