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)
• xL “proof” y, |y|≤p(|x|) that P can send to V to
convince him, i.e. V(x,y) accepts (completeness)
• xL “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 = y1y2 y3 … yr. y1,y2,…,yr)
Prover P Disprover D
unlimited
power
unlimited
power
• xL P D, Prover P can convince V (completeness)
• xL 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
• xL P. Pr[ V interacting with P accepts] ¾
• xL 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 xL else xL.
• 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+1mj+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
Asuch 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 A0 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= Aand 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 = 2degree, 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 a0 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 gf. 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