CS 789 THEORY SEMINAR [home]

Speaker:  Hubert Chen
Affiliation: Cornell University, Computer Science
Date: Monday, November 25, 2002
Title: Inverse NP Problems: Witnesses in Search of a Crime

Abstract:

One characterization of the class NP is that it contains those 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.

We study the complexity of deciding, given a set $\Pi$ of proofs, whether or not there exists some $x$ inducing $\Pi$ (relative to a particular verifier) -- that is, if there exists an $x$ with exactly $\Pi$ as its set of proofs. We call this decision problem the inverse problem for the verifier. A particular example would be INVERSE 3-SAT: given a set of assignments $\Pi$ on a variable set $V$, decide if there is a 3-SAT formula (on $V$) with exactly $\Pi$ as its set of satisfying assignments.

We develop a new notion of reduction, called \pi-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, including K-CLIQUE, EXACT COVER, KNAPSACK, STEINER TREE, and PARTITION.

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-complete inverse problem is exhibited, yielding a new and natural example of a Sigma_2-complete problem.