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:
Prover and Verifier share the input formula
Prover sends to the Verifier a set of variables assigned to True, which should be the minimum
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?