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.