Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I have to sketch an IP proof for the minSAT problem. The minSAT problem is define in this way:

  • For a given formulae find a satisfying assignment with a min subset of variables assigned to True;

My sketched IP protocol is:

  1. Prover and Verifier share the input formula

  2. Prover sends to the Verifier a set of variables assigned to True, which should be the minimum

  3. Verifier checks if the given set indeed satisfies the formula. If it is the case, it chooses one variable, re-computes the formula and sends the new formula to the Prover

I would iterate this process untill the Prover gives an empty set or I reach a contradiction.

My questions are:

  • Is this a right protocol? If not, how can I exploit the cases in which the protocol doesn't work?

  • How can I evaluate the probability of completness and soundness for this protocol?

share|improve this question

1 Answer 1

Your protocol is not very clear. What do you mean at step 3 by "it chooses one variable, re-computes the formula"?

I assume the verifier just set that variable to 1 and re-computes the formula without that variable.

Then, this protocol still have some problems. Let say that there are two sets of variables that satisfy the formula: $\{x\}$ and $\{y,z\}$. The minSat is $x$. But what happens if the prover say it is $y,z$? the verifier will check it, will see this set satisfies the formula, remove, say $y$ and send the formula back to the prover. The prover will then reply with $\{z\}$ and the verifier will accept it.

Even if the verifier renames the variables in a random way, (say, replace $x$ with $a$ and $z$ with $b$), it's not clear this protocol works. Still, maybe the prover is able to identify the variable that previously was $z$ from the structure of the formula, and on the second level it will return the output $z$.

In order for your protocol to work you need the prover not to be able to answer you consistently with the wrong answer, and it is not clear how your protocol achieves this. So although it might be sound (prover cannot give a set that doesn't satisfies the formula), it will not be correct (prover can give a non-minimal set).

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.