cover_image

TQBF is in IP

Kurt Pan XPTY
2020年12月24日 14:16

Let  be a quantified Boolean formula of the form

where  is a cnf-formula and each  is  or .

For  and  let

where  is  with  through  substituted for  through 

Thus,  is the truth value of . We then have the arithmetic identities

Define  to be .

To keep the degrees of the polynomials small, we introduce a reduction operation  that reduces the degrees of polynomials without changing their behavior on Boolean inputs.

where each  and 

For each  we define the function  We define  to be the polynomial obtained by arithmetizing  For $i<k,$ we="" define="" $f_{i}$="" in="" terms="" of="" $f_{i+1}$="" :<="" p="">


If  is  or  has one fewer input variable than  does. If  is , the two functions have the same number of input variables. Thus, function  will not, in general, depend on  variables.

Note that the  operation on polynomials doesn't change their values on Boolean inputs. Therefore,  is still the truth value of . However, note that the  operation produces a result that is linear in  We added  after  in  in order to reduce the degree of each variable to 1 prior to the squaring due to arithmetizing 

Now we are ready to describe the protocol. All arithmetic operations in this protocol are over a field  of size at least  where  is the length of  .

  • Phase 0.  sends   sends  to   checks that  and s if not.
  • Phase  .  persuades  that  is correct if  is correct.   sends the coefficients of  as a polynomial in   uses these coefficients to evaluate  and   checks that these identities hold:

and

If not,  .  picks a random  in  and sends it to 

  • Phase  .  checks directly that  is correct.   evaluates  to compare with the value  has for  If they are equal,  ; otherwise,  .

Clearly, if  is true,  can follow the protocol and  will accept. If  is false,  must lie at phase 0 by sending an incorrect value for  At phase  if  has an incorrect value for  one of the values and  must be incorrect and the polynomial for  must be incorrect. Consequently, for a random the probability that  gets lucky at this phase because  is correct is at most the polynomial degree divided by the field size or . The protocol proceeds for  phases, so the probability that  gets lucky at some phase is at most  If  is never lucky,  will reject at phase