Abstract of Paper |

*Inverse NP Problems*

by Hubie Chen

**Abstract:**

One characterization of the class NP is as the class of all languages for which there exists a verifier, operating in polynomial time, 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$ as a member. This paper studies the complexity of deciding, given a set $\Pi$ of proofs, whether or not there exists some $x$ inducing $\Pi$ (relative to a particular verifier). We call this decision problem the inverse problem for the verifier. We develop a new notion of reduction which allows one to compare the complexity of inverse problems. Using this notion, we classify as coNP-complete the inverse problem for the ``natural'' verifiers of many NP-complete problems. We also show that the inverse complexity of a verifier for a language $L$ cannot be predicted solely from the complexity of $L$, but rather, is highly dependent upon the choice of verifier used to accept $L$. In this context, a verifier with a $\Sigma_2^p$-complete inverse problem is exhibited, giving a new and natural example of a $\Sigma_2^p$-complete problem.