#SAT is in IP
Say that has variables through . Let be the function where for and we set equal to the number of satisfying assignments of such that each for The constant function is the number of satisfying assignments of The function is 1 if those 's satisfy otherwise, it is An easy identity holds for every and
The protocol for begins with phase 0 and ends with phase The input is the pair .
Phase 0. sends to . checks that and if not. Phase 1. sends and to . checks that and if not. Phase 2. sends and to . checks that and and if not. ... Phase . sends for each assignment to the 's. checks the equations linking with and if any fail. Phase . checks that the values are correct for each assignment to the 's by evaluating on each assignment. If all assignments are correct, ; otherwise, .
This protocol doesn't provide a proof that is in IP because the Verifier must spend exponential time just to read the exponentially long messages that the Prover sends. Let's examine it for correctness anyway because that helps us understand the next, more efficient protocol.
Intuitively, a protocol decides a language if a Prover can convince the Verifier of the membership of strings in In other words, if a string is a member of , some Prover can cause the Verifier to accept with high probability. If the string isn't a member of , no Prover - not even a crooked or devious one-can cause the Verifier to accept with more than low probability. We use the symbol to designate the Prover that correctly follows the protocol, and that thereby makes accept with high probability when the input is in We use the symbol to designate any Prover that interacts with the Verifier when the input isn't in Think of as an adversary -as though were attempting to make accept when should reject. The notation is suggestive of a "crooked" Prover.
In the protocol we just described, the Verifier ignores its random input and operates deterministically once the Prover has been selected. To prove the protocol is correct, we establish two facts. First, if is the correct number of satisfying assignments for in the input some Prover causes to accept. The Prover that gives accurate responses at every phase does the job. Second, if isn't correct, every Prover causes to reject. We argue this case as follows.
If is not correct and gives accurate responses, rejects outright in phase 0 because is the number of 's satisfying assignments and therefore To prevent from rejecting in phase must send an incorrect value for denoted Intuitively, is a lie about the value of As in real life, lies beget lies, and is forced to continue lying about other values of in order to avoid being caught during later phases. Eventually these lies catch up with in phase where checks the values of directly.
More precisely, because at least one of the values and that sends in phase 1 must be incorrect; otherwise, rejects when it checks whether Let's say that is incorrect and call the value that is sent instead Continuing in this way, we see that at every phase must end up sending some incorrect value or would have rejected by that point. But when checks the incorrect value in phase it rejects anyway. Thus, we have shown that if is incorrect, rejects no matter what does. Therefore, the protocol is correct.
The problem with this protocol is that the number of messages doubles with every phase. This doubling occurs because the Verifier requires the two values and to confirm the one value If we could find a way for the Verifier to confirm a value of with only a single value of , the number of messages wouldn't grow at all. We can do so by extending the functions to non-Boolean inputs and confirming the single value for some selected at random from a finite field.
:
In a technique called arithmetization, we associate with a polynomial where mimics by simulating the Boolean and operations with the arithmetic operations and as follows. If and are subformulas, we replace expressions
One observation regarding that will be important to us later is that the degree of any of its variables is not large. The operations and each produce a polynomial whose degree is at most the sum of the degrees of the polynomials for and Thus, the degree of any variable is at most the length of .
If 's variables are assigned Boolean values, it agrees with on that assignment. Evaluating when the variables are assigned non-Boolean values has no obvious interpretation in However, the proof uses such assignments anyway to analyze . The variables range over a finite field with elements, where is at least
We use to redefine the functions that we defined in the proof idea section. For and for let
Observe that this redefinition extends the original definition because the two agree when through take on Boolean values. Thus, is still the number of satisfying assignments of Each of the functions can be expressed as a polynomial in through The degree of each of these polynomials is at most that of .
Next, we present the protocol for . Initially, receives input and arithmetizes to obtain polynomial All arithmetic is done in the field with elements, where is a prime that is larger than . A comment in double brackets appears at the start of the description of each phase.
Phase 0. sends sends to checks that rejects if that fails. Phase 1. persuades that is correct if is correct. sends the coefficients of as a polynomial in uses these coefficients to evaluate and checks that and if not. (Remember that all calculations are done over selects at random from and sends it to Phase 2. persuades that is correct if is correct. sends the coefficients of as a polynomial in uses these coefficients to evaluate and checks that and if not. selects at random from and sends it to ... Phase . persuades that is correct if is correct. sends the coefficients of as a polynomial in uses these coefficients to evaluate and checks that and if not. selects at random from and sends it to ... Phase . checks directly that is correct. evaluates to compare with the value has for If they are equal, ; otherwise, .
Now we show that this protocol decides . First, if has satisfying assignments, obviously accepts with certainty if Prover follows the protocol. Second, we show that if doesn't have assignments, no Prover can make it accept with more than a low probability. Let be any Prover.
To prevent from rejecting outright, must send an incorrect value for in phase Therefore, in phase one of the values that calculates for and must be incorrect. Thus, the coefficients that sent for as a polynomial in must be wrong. Let be the function that these coefficients represent instead. Next comes a key step of the proof.
When picks a random in we claim that is unlikely to equal For we show that
That bound on the probability follows from Lemma: A polynomial in a single variable of degree at most can have no more than roots, unless it always evaluates to Therefore, any two polynomials in a single variable of degree at most can agree in at most places, unless they agree everywhere. Recall that the degree of the polynomial for is at most and that rejects if the degree of the polynomial sends for is greater than We have already determined that these functions don't agree everywhere, so Lemma implies they can agree in at most places. The size of is greater than The chance that happens to be one of the places where the functions agree is at most which is less than for
To recap what we've shown so far, if is wrong, 's polynomial must be wrong, and then would likely be wrong by virtue of the preceding claim. In the unlikely event that agrees with was "lucky" at this phase and it will be able to make accept (even though should reject) by following the instructions for in the rest of the protocol.
Continuing further with the argument, if were wrong, at least one of the values computes for and in phase 2 must be wrong, so the coefficients that sent for as a polynomial in must be wrong. Let be the function these coefficients represent instead. The polynomials for and have degree at most So as before, the probability that they agree at a random in is at most Thus, when picks at random, is likely to be wrong.
The general case follows in the same way to show that for each if
then for and for chosen at random in
Thus, by giving an incorrect value for is probably forced to give incorrect values for and so on to The probability that gets lucky because selects an where even though and are different in some phase, is at most the number of phases times or at most If never gets lucky, it eventually sends an incorrect value for But checks that value of directly in phase and will catch any error at that point. So if is not the number of satisfying assignments of no Prover can make the Verifier accept with probability greater than .
To complete the proof of the theorem, we need only show that the Verifier operates in probabilistic polynomial time, which is obvious from its description.