2023年11月25日

计算理论代写｜Homework 4 Interactive Proofs and the Class IP

这是一个美国的计算理论和计算复杂性作业代写

Recall from class that the function f : f0; 1g∗ ! f0; 1g is in IP[k] if there exists a polynomial time
PTM V (the verifier), a (possibly randomized) function P : f0; 1g∗ ! f0; 1g∗ (the prover) and a
k−round interactive protocol between P and V, denoted hP; Vi such that for all x 2 f0; 1g∗:

• Completeness: if f(x) = 1 then PrhP; Vi(x) = 1 ≥ 2=3;

• Soundness: if f(x) = 0 then for all P∗ : f0; 1g∗ ! f0; 1g∗, PrhP∗; Vi(x) = 0 ≥ 2=3 (P∗ de

notes an adversarial prover function which might deviate from the protocol specifications).

Here, hP; Vi(x) denotes the output bit of V after the protocol is run on input x. Recall that the
complexity class IP is Sc≥1 IP[nc], the set of functions which can be computed by an interactive
proof system with a polynomial number of rounds. Recall from class that we showed that any
f : f0; 1g∗ ! f0; 1g which can be computed by an interactive proof system with a deterministic
verifier must be in NP. Thus, it is critical for the definition of IP that V be probabilistic. In this
first exercise, we will understand a bit about what can be said about the prover.

IP ⊂ PSPACE

In this section, suppose f : f0; 1g∗ ! f0; 1g can be computed by a 3−round interactive proof sys
tem hP; Vi, where P the first and third message, V sends the second. Let P1; P3 : f0; 1g∗ ! f0; 1g∗
denote the prover’s function for determining its first and third round messages, respectively. So
syntactically, the bit hP; Vi(x) is computed as follows:

· P sends a1 to V where a1 ∼ P1(x);
· V sends a2 to P where a2 ∼ V2(x; a1);
· P sends a3 to V where a3 ∼ P3(x; a1; a2);
· V outputs b 2 f0; 1g where b = Vout(x; a1; a2; a3).

Now, define the functions val0; val1; val2; val3 : f0; 1g∗ ! R to be the expected values of the output
bit b, given the protocol so far. So specifically,

· val3(x; a1; a2; a3) = Vout(x; a1; a2; a3) 2 f0; 1g;
· val2(x; a1; a2) = Ea3∼P3(x;a1;a2)val3(x; a1; a2; a3);
· val1(x; a1) = Ea2∼V2(x;a1)val2(x; a1; a2);
· val0(x) = Ea1∼P1(x)val1(x; a1);

Note that val0(x) = PrhP; Vi(x) = 1.

Problem 1. Define another, deterministic prover P0 where P0 1; P0 3 : f0; 1g∗ ! f0; 1g∗ work as
follows:

· P01(x) outputs a1 such that val1(x; a1) is optimal (breaking ties arbitrarily);

· P03(x; a1; a2) outputs a3 such that val3(x; a1; a2; a3) is optimal (breaking ties arbitrarily).

For i = 0; 1; 2; 3, define val0 i analogously to vali except with the new prover P0 replacing the
old prover P.

(a) Prove that val0 0(x) ≥ val0(x) for all x 2 f0; 1g∗. Deduce that the new protocol satisfies the
completeness property; namely, deduce that when f(x) = 1, PrhP0; Vi(x) = 1 ≥ 2=3.

(b) Prove that if f(x) = 0, then PrhP∗; Vi(x) = 0 ≥ 2=3 for all P∗.

(c) Now prove that the functions P0 3 and P0 1 can be computed by a polynomial space TM.

(d) Deduce that any f 2 IP[3] can be computed by an interactive proof system where P is
implemented by a deterministic, polynomial space TM. Since V is a polynomial time PTM,
and the computation of any polynomial time PTM can be also computed by a deterministic
polynomial space TM, this implies that IP[3] ⊂ PSPACE. This holds more generally for
protocols with more rounds; we focused on 3−round protocols for simplicity only. Thus,
we have shown that IP ⊂ PSPACE!