InteractiveProof

Back to NP: 

Back to NP LNP iff members have short, efficiently checkable, certificates of membership. Is  satisfiable? 

Interactive Protocols: 

Interactive Protocols Two new ingredients: Several rounds Randomness

Interactive Proofs Formally: 

Interactive Proofs Formally Interactive Proof System for L is a game: Completeness: There is a prover strategy P, s.t for xL, P convinces V with probability  ⅔. Soundness: For xL, any prover strategy P* convinces V with probability  ⅓. probabilistic polynomial-time verifier unlimited prover Vs.

The Players: 

The Players A verifier is a polynomial function: input  random-string  past-interaction  reply A prover is a function: input  past-interaction  reply all previous prover and verifier replies

Example: Graph Non-Isomorphism: 

Example: Graph Non-Isomorphism Input: Two graphs G=(V,E), G’=(V’,E’). Question: Does for every 1-1 map f of V onto V’ exist v,uV s.t (v,u)E but (f(v),f(u))E’ (or (v,u)E, but (f(v),f(u))E’ )?

Are They Isomorphic?: 

Are They Isomorphic?

IP for Non-Isomorphism: 

IP for Non-Isomorphism common input chooses one of the graphs at random. send P an isomorphic graph. answers which graph was chosen. 2 OK! 1 2

Correctness: 

Correctness Completeness: non-isomorphic graphs  P can check which is isomorphic to the sent one. Soundness: isomorphic graphs  both isomorphic to the sent one. P succeeds with probability ½.

IP: 

IP Definition: IP is the class of all languages having interactive protocols with polynomial number of rounds.

Easy Claims: 

Easy Claims Claim: NPIP. Proof’s Idea: Every NP proof is also an IP proof. Claim: If LIP, and it has a verifier that does not flip coins, then LNP. Proof’s Idea: P would provide the answers for all V’s questions in advance.

Amplification: 

Amplification Observation: The constants ⅓ and ⅔ in the definition can be amplified to probabilities 1-2-p(.) and 2-p(.), for any polynomial p(.). Proof’s Sketch: Given a protocol which is correct with probability ⅔, repeat it p(.) times independently. Apply Chernoff’s inequality.

Arthur-Merlin Games: 

Arthur-Merlin Games … The prover (M for Merlin) is a function of the random string of the verifier (A for Arthur) as well. Define AM/MA – according to who gets to start.

Easy Claim: 

Easy Claim Claim: AMIP. Proof’s Idea: If A is convinced when he assumes M is that powerful, he is surely convinced when M is only less powerful.

The Graph Non-Isomorphism Example Revisited: 

The Graph Non-Isomorphism Example Revisited Is the graph non-isomorphism protocol, also an AM protocol? No! M knows which graph was chosen! Is there an AM protocol for this language?

IP and AM: 

IP and AM Theorem (without proof): IP=AM i.e, knowing the random string essentially does not increase M’s power.

IP=PSPACE [Shamir90]: 

IP=PSPACE [Shamir90]   given a verifier, construct an optimal prover using poly-space show the PSPACE-complete TQBF is in IP

Optimal Prover: 

Optimal Prover . . . possible verifier coin tosses [defines verifier’s reply] . . . . . . . . . rounds best prover reply ? ? ? ? ? ? find recursively prover reply most probable to result in acceptance

Poly-Space Is Sufficient for the Prover: 

Poly-Space Is Sufficient for the Prover Claim: IPPSPACE Proof: Given a verifier, the optimal strategy for the prover may be computed in poly-space. [as described above]

TQBF: 

TQBF Instance: A quantified Boolean formula =x1x2…xm[(x1,…,xm)] Goal: Is  true? x1x2x3 (x10  (x2>0  (|x3|<x2  |sinx3/x3-1|<x1))

TQBF and PSPACE: 

TQBF and PSPACE Claim (without proof): TQBF is PSPACE-Complete.

The Proof: Evaluation Tree: 

The Proof: Evaluation Tree . . . . . . x1=0 x1=1  x1=0 x1=1  x1x2 … (x1,x2,…) x2 … (0,x2,…) x2 … (1,x2,…) …(0,0,…) …(0,1,…) (0,0,..,0) (0,0,..,1) (0,0,...,1,0) (0,0,...,1,1) I can’t scan the entire tree!

IP for TQBF: 

IP for TQBF We’ll show the verifier may be convinced (with reasonable confidence) even without scanning the entire (exponential) proof specified by the prover.

First Idea: 

First Idea Represent the QBF by a polynomial.

Arithmization: 

Arithmization  xi   1-  xi 1-(1-)(1-) F 0 T 1 x (x) x (x) (0)(1) (0)(1)

Polynomials: Basic Facts: 

Polynomials: Basic Facts Claim: A polynomial of degree ≤ r on d variables over a field F may have ≤ r|F|d-1 roots, unless it is identically zero. Corollary: Two polynomials of degree ≤ r on d variables over a field F may agree on ≤ r|F|d-1 places, unless they agree everywhere.

Polynomials: Basic Facts: 

Polynomials: Basic Facts Corollary: Two different polynomials of degree ≤ r over a field F agree on a random point with probability ≤ r/|F|.

Low Degree Extension: 

Low Degree Extension . . . . . . P1() P2(x1) P3(x1,x2) Pm(x1,…,xm) . . . . . . We can evaluate on a larger field! . . . . . . . . .

How To Convince?: 

How To Convince? Check a random path! P1() P2(x1) P3(x1,x2) Pm(x1,…,xm) . . . . . . . . . . . . . . . . . . . . .

How To Convince?: 

How To Convince? P1() P2(x1) P3(x1,x2) Pm(x1,…,xm) . . . . . . . . . . . . . . . . . . . . . verify this is 1 verify P2(x1) could have resulted P1(). verify P3(r1,x2) could have resulted P2(r1). verify Pm(r1,…,rm-1,xm) could have resulted Pm-1(r1,…,rm-1). r1 r2 check Pm(r1,…,rm).

Example: 

Example What would an honest prover do, given the formula:x1x2 (x1x2) ? x1x2 1- (1-x1∙0)(1-x1∙1) = x1 0∙1 = 0 verify this is 1  . . . . . . . . .

Example: 

Example What would a (dishonest) prover might do, given the formula:x1x2 (x1x2) ? x1x2 1 1 verify this is 1  verify P2(x1)=1 could have resulted P1().  1∙1 = 1 . . . . . . . . . 1 verify P3(1,x2)=x2 could have resulted P2(1). 5 1-(1-0)(1-1) = 1  check P3(1,5). 

Correctness: 

Correctness Completeness: If the formula is true, the prover may compute the true polynomials, and the verifier will always accept. Soundness: What if the formula is not true?

If The Formula Is False…: 

If The Formula Is False… P1() P2(x1) P3(x1,x2) Pm(x1,…,xm) . . . . . . . . . . . . . . . . . . . . . if this is not 1, we immediately reject if this is not the real Pm(x1,…,xm), we also immediately reject If we nevertheless accept, we get fooled somewhere!

Soundness: 

Soundness The probability we get fooled at some specific level is ≤ r/|F|, where r bounds the polynomials’ degrees. The probability we get fooled somewhere down the path is ≤ mr/|F| [union-bound] |F| can be made polynomially large in m. the two different polynomials agree on a random point

Bound The Degrees: 

Bound The Degrees Alas, the degree of the polynomials might be exponential in m, as each stage up might double it! To solve this problem, we’ll somewhat lengthen the tree, but make sure the degrees are kept small.

Auxiliary Quantifier: 

Auxiliary Quantifier Suppose now we have a QBF =Q1x1...Qmxm[]. ’=Q1x1R1x1Q2x2R1x1R2x2...QmxmR1x1...Rmxm[]. R is an auxiliary quantifier, designed to keep the degree of the polynomials small. We’ll arithmetize it as follows: Rx (x)  (1-x)∙(0) + x∙(1) The degree of x is made 1. The value remains the same for 0-1 variables

Summing Up: 

Summing Up Now we can apply the former analysis, and get that PSAPCEIP, Hence IP=PSPACE.

Multi-Prover Interactive Protocol: 

Multi-Prover Interactive Protocol poly many provers

What is MIP?: 

What is MIP? Theorem (without proof): MIP=NEXP

Scaling-Down: 

Scaling-Down Similarly, one can show NP is contained in MIP with O(1) provers and O(logn) random bits. Interestingly, this has implications to hardness of approximation TO BE CONTINUED…