程序代写代做代考 algorithm Microsoft PowerPoint – lecture26 [Compatibility Mode]

Microsoft PowerPoint – lecture26 [Compatibility Mode]

COMS4236: Introduction to
Computational Complexity

Spring 2018

Mihalis Yannakakis

Lecture 26, 4/19/18

Outline
Interactive Proofs
• Class IP
• IP = PSPACE
• Boolean formulas and arithmetization

NP proof

instance x

Prover P Verifier Vproof y
unlimited

power
polynomial

time
(certificate)

• xL   “proof” y, |y|≤p(|x|) that P can send to V to
convince him, i.e. V(x,y) accepts (completeness)

• xL   “proof” y, |y|≤p(|x|) that P sends to V, it
does not convince him, i.e. V(x,y) rejects (soundness)

PSPACE proof with alternation
instance x = y1y2 y3 … yr. y1,y2,…,yr)

Prover P Disprover D
unlimited

power
unlimited

power

• xL  P D, Prover P can convince V (completeness)

• xL  D P, Disprover D can convince V (soundness)

y1
y2

yr

Verifier V
poly-time

Interactive proofs: Class IP
instance x

Prover P Verifier V
unlimited

power

poly-time +
randomness

• xL  P. Pr[ V interacting with P accepts]  ¾

• xL  P. Pr[ V interacting with P accepts] ≤ ¼

m1
m2

mr

(completeness)

(soundness)

• Size of messages and # rounds of the protocol ≤ poly(|x|)

• V: x, history, random choices  next message/accept/reject

Interaction without randomness = no help

• If V is a deterministic polynomial time algorithm
interacting with a prover (of unlimited power), then
interaction does not help: can only accept NP languages

• Reason: Prover can generate the whole complete
interaction and send it to the Verifier at the beginning in
one message.

• Then Verifier can check its consistency and accept.

Interaction with Randomness: it helps

• Probability ¼ – ¾ arbitrary: could again reduce error by
repetition

• IP contains NP (no randomness)
• IP also contains BPP (no Prover)

• But it contains lots more.

Example: Graph Non-Isomorphism

Graph Isomorphism:
• Input: Two graphs G1=(N1,E1), G2=(N2,E2)
• Question: Are the graphs isomorphic,
i.e.  1-1 onto mapping N1  N2 s.t. (u,v)E1 iff

(u),v)) E2 ?

Graph Isomorphism  NP, but not known (and not
believed) to be NP-complete

Graph-Nonisomorphism  coNP, not known to be in NP
It is in IP

Interactive protocol for
Graph Non-Isomorphism

• V picks at random i=1 or 2
V picks a random 1-1 mapping : Ni{1,…,n} and sends
to P the graph H = (Gi) (i.e. Gi with nodes relabeled
according to )

• P sends to V the index j=1 or 2 of the graph G1 or G2 that
is isomorphic to H

• V accepts if j=i

Interactive protocol for
Graph Non-Isomorphism

• G1, G2 not isomorphic  P can always give the right
index  Prob =1

• G1, G2 isomorphic  P has only Prob ½ of giving the
right index

• Repeat k times to reduce probability of error to

• Zero-knowledge proof: V is convinced of the answer but
does not learn anything else beyond this, for example
nothing that would help convince another party (unlike
the NP-type proofs)

2 k

IP = PSPACE
• IP  PSPACE
• L IP: There is an interactive protocol between Verifier V

(randomized poly-time algorithm) and prover P with p(n)
rounds, each message of length p(n).

• Can assume wlog that V flips all the random coins at the
start, i.e. generates a random string z at beginning.

• Assume wlog that V sends the first message, there are
p=p(n) rounds, and in the last message V sends its
decision (accept/reject).

• Given input x: Compute in PSPACE the maximum
probability, over all provers P, that V accepts x when
interacting with P. If  ¾ then xL else xL.

• Use a recursive algorithm.

IP  PSPACE
• For input x, and (m1,m2…,mj) a tuple of j messages

exchanged (a prefix of the interaction, j=0,…,p), compute
• Value(x,  =maximum {over all P} probability that V accepts

for the given x, and interaction prefix 
• if j=p then { if mj=accept then return 1 else 0 }

else if j=odd (P’s turn next: choose best message for P)
then return max { Value(x,(mj+1mj+1|≤ p(|x|) }

else (V’s turn) return
j+1

z j+1 j+1
m

Pr [V(x,z,β)=m ] Value(x,(β,m ))

Main: Return Value(x,) (=empty tuple – no messages)

• Depth of recursion polynomial.
Note: can compute Prz[V(x,z,)=mj+1] in PSPACE

PSPACE  IP
• Suffices to give interactive protocol for Q3SAT.
• Input F = y1 y2 y3… ym y1,y2,…,ym)

where = C1  C2  …  Ck
Step 1. Transform given expression F to an equivalent

“simple” expression : no occurrence of a variable
separated from its quantification by more than one 

The simple expression is not in prenex form, but the
quantifiers are all still nested.

Step 2. Transform simple formula  to arithmetic expression
Asuch that  is true iff A>0

Step 3. Interactive protocol to test if A>0

1. Transformation to “simple” expression
Qx

y

x

Qx

y

x’

x’


 

x’x x x’
x=x’Do the transformation top-

down in the parse tree of the
formula at every  node

 new formula of size O(n²)

Example
x

y

(x,y,z)

z

x
y

x’


 

x’x x x’

z
x’’

y’

(x’’,y’,z)

x=x’

x’=x’’

y=y’

At every  node introduce
fresh versions of the higher
variables

2. Arithmetization of QBF

• Boolean variables  arithmetic variables
• negative literal  1-x
• conjunction   multiplication ⋅
• disjunction   addition +

• x 

• x 

x


1

x 0


1

x 0

• The arithmetization can be applied more generally to any
quantified Boolean formula in which all negations are
applied directly to variables

Example

           x y[(x y) (x y) z((y z) (x z))]


 

          
11 1

x 0 z 0y 0
A [(x y) (x (1 y)) ((y z) (x (1 z)))]

Note: A can be doubly exponential in value

   

    
k

1 21 2 k

1 1 1 1 1
2

1 2
y 0 y 0x 0 x 0 x 0

(y y ) 4

Properties
1. The QBF is true (resp. false) iff A is >0 (resp. =0)

Proof: Straightforward induction.

2.
Proof: Every + ,  at most doubles the value. Every ⋅,  at

most squares it.

3. A is >0 iff there is a prime p between 2n and 23n such
that A ≠ 0 mod p.

Proof: By the prime number theorem, there are
~ 23n/ln(23n) > 22n prime numbers < 23n If A0 mod all prime p in [2n, 23n ] then A is divisible by their product which is >

n2
φA 2

n22

3. Interactive Protocol for A
• First, P sends V a prime p in [2ⁿ, 23n] and the value

a = A mod p (≠ 0), along with the proof of primality of p.
• Thereafter, there is an arithmetic expression A (starting with

 or  and a value v (a number mod p) which P claims is =
A mod p

Initially A= Aand v =a

• Each round eliminates one or , the outermost one.
1 1

0 0
‘( ) or ‘( )

x x
A A x A A x

 

  

• Expression A’(x) is equal to a polynomial f(x) in x.

Interactive Protocol for A

• Expression A’(x) is equal to a polynomial f(x) in x.

• Since is simple, degree of f(x) is ≤2n
Proof: By induction on subexpression: If no with an

occurrence of x in its scope then degree ≤n, else ≤2n.
How is degree affected by operations?
+ or   degree=max degree, size = sum of sizes, or = size
  degree = sum of degrees, size = sum of sizes
 degree = 2degree, size =same.
But cannot have two nested ’s with an occurrence of x in the
scope because expression is simple

Round of Interactive Protocol for A
• P sends to V the polynomial f (x)= A’(x) (i.e., all the

coefficients mod p, at most 2n of them)
• V verifies that f(0)+f(1)=a (mod p) or f(0)f(1)=a (mod p)

(depending on whether A= A’(x) or A= A’(x) )
• If not, then V rejects
• V chooses a random value rÎ[0,p-1] for x and sends it to P

• By construction of the simple formula, either the expression
A’(r) (i.e. expression A’ with r substituted for x) starts with a
or or has no or or A’(r) is of the form A’’(r)⋅h(r),
where A’’ starts with or  and h has no or .

• In the former case let B=A’(r), b=f(r); in the latter case let
B=A’’(r), b=f(r)/h(r) mod p.

• P and V go on to the next round with the expression B in
place of A, and the value b in place of a,

Goal is to verify that the expression B has value b mod p

End of Interactive Protocol for A

• Protocol continues like this until all  are eliminated.

• Then V can evaluate on its own the expression and
check whether it is = value mod p. If yes, then V accepts,
else it rejects.

Analysis
• If A(i.e.  is true), then the Prover can play honestly

and convince the Verifier.
• If A(i.e.  is false), then no matter which prime p the

Prover picks and value a0 he sends, A mod p  a
• P cannot send the correct polynomial f(x) for A’ because

then he will be caught, eg. f(0)+f(1) =0  a.
Must send a wrong polynomial gf. The two polynomials
agree in at most 2n values (≤degree)  with probability

2 2
1 1

2n
n n
p

   V picks a r such that g(r) f(r)=A’(r).

• Then, either B=A’(r) and b=g(r) B, or

A’(r)=A’’(r)⋅h(r) and B=A’’(r), b=g(r)/h(r) B again

 the inconsistency between the expression and the value
propagates to the next round with probability 1-2n/2ⁿ.

Analysis ctd.

 If A=0 (i.e. is false), then with probability

the inconsistency will propagate to the last round

and V will reject

4
3

2
2

1 




n

n

n