10.5

Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Theorem 10.24

Proof

We are going to show that $c10-math-1253$ for all k ≥ 1. The theorem then follows from Theorem 10.18. Let $c10-math-1255$ , with k ≥ 1. Let $c10-math-1257$ be an interactive proof system for L with error $c10-math-1259$ , such that each query and each answer of $c10-math-1260$ is of length exactly q(n) and $c10-math-1262$ uses exactly r(n) random bits, where q(n) and r(n) are two polynomial functions. Without loss of generality, we assume that $c10-math-1266$ for all n ≥ 0. From Proposition 10.7(c) (and Exercise 10.2), we may assume that $c10-math-1268$ . We let $c10-math-1269$ be defined as in the proof of Theorem 10.21.

We first describe the idea of how the new Arthur–Merlin proof system simulates the interactive proof system $c10-math-1270$ . In Stage 1 of the previous Arthur–Merlin proof system A₁, Merlin tried to convince Arthur that $c10-math-1272$ by sending the values $c10-math-1273$ to Arthur for all y of length q(n) and letting Arthur randomly select a string y to test whether Merlin's values $c10-math-1277$ are correct. As there are exponentially many such values $c10-math-1278$ , we cannot afford to do this. Instead, in our new Arthur–Merlin proof system A₂, Merlin makes an assertion that for “many” strings u, $c10-math-1281$ is “large.” That is, Merlin sends parameters c₁ and c₂ to Arthur, claiming that there are about $c10-math-1284$ strings u satisfying $c10-math-1286$ . How does Arthur test this claim? Note that if Merlin's claim is true, then $c10-math-1287$ satisfies $c10-math-1288$ and so, by Lemma 10.23(b), with high probability $c10-math-1289$ for the set H of random hashing functions and the random set $c10-math-1291$ chosen by Arthur. On the other hand, if Merlin was cheating, then $c10-math-1292$ is very small and, by Lemma 10.23(c), with high probability $c10-math-1293$ . Based on the above observations, Arthur tests Merlin's claim as follows: He selects $c10-math-1294$ random linear hashing functions $c10-math-1295$ and m² random strings $c10-math-1297$ of length c₁ and sends $c10-math-1299$ and $c10-math-1300$ to Merlin, asking Merlin to find a string $c10-math-1301$ such that $c10-math-1302$ . If Merlin passes this test, then they enter the next stage, in which Merlin tries to convince Arthur that $c10-math-1303$ is indeed of size about $c10-math-1304$ , and Arthur applies the same test to this claim.

In the following, we give a formal proof for the case k = 1, that is, when M_v makes only one query to f_p. The proof is easily extended to the general case when k > 1. We leave it as an exercise (Exercise 10.12).

Arthur–Merlin Proof System A₂ for L (k = 1).

Input: x, $c10-math-1313$ .

Stage 1. (1) Merlin sends an integer c₁ to Arthur. (Merlin claims that $c10-math-1315$ , where $c10-math-1316$ for some c₂ to be sent later.)

(2) Arthur selects a collection of random linear hashing functions $c10-math-1318$ from $c10-math-1319$ to $c10-math-1320$ , and a set of random strings $c10-math-1321$ , and sends them to Merlin.

(3) Merlin sends two strings $c10-math-1322$ to Arthur.

(4) Arthur verifies that $c10-math-1323$ ; he rejects if this does not hold.

Stage 2. (1) Merlin sends an integer c₂ to Arthur. (Merlin claims that $c10-math-1325$ .)

(2) Arthur selects random linear hashing functions $c10-math-1326$ from $c10-math-1327$ to $c10-math-1328$ and $c10-math-1329$ random strings $c10-math-1330$ .

(3) Merlin sends a string α of length r(n) to Arthur.

(4) Arthur checks that $c10-math-1333$ . Arthur also checks whether $c10-math-1334$ is an accepting history h_x,α with respect to string α.

(5) Arthur accepts if $c10-math-1337$ ; he rejects otherwise.

To see that the above Arthur–Merlin proof system A₂ works correctly, we first show that for all $c10-math-1339$ , the system A₂ accepts x with probability at least $c10-math-1342$ , which is $c10-math-1343$ by the assumption of $c10-math-1344$ . To do this, we describe Merlin's algorithm for calculating c₁ and c₂:

Honest Merlin of System A₂.

Stage 1, step (1). For any j, $c10-math-1349$ , let

Let j₁ be the integer between 1 and r(n) that maximizes $c10-math-1353$ . Merlin lets $c10-math-1354$ .

Stage 1, step (3). After he receives H₁ and V₁, Merlin finds a string $c10-math-1357$ , if such a string exists; otherwise, Merlin sends “failure.” Next, Merlin finds z that maximizes $c10-math-1359$ and sends y,z to Arthur.

Stage 2, step (1). Merlin lets $c10-math-1361$ .

Stage 2, step (3). Merlin finds a string $c10-math-1362$ if such a string exists; otherwise he sends “failure.”

We note that because $c10-math-1363$ , the probability of $c10-math-1364$ is at least $c10-math-1365$ . This means that the probability of Merlin failing at step (3) of Stage 1 is at most $c10-math-1366$ . Similarly, the probability of Merlin failing at step (3) of Stage 2 is also bounded by $c10-math-1367$ . Finally, we claim that it is always true that $c10-math-1368$ . It then follows that the probability of Arthur accepting the input is at least $c10-math-1369$ .

To prove that $c10-math-1370$ , we first show that for any $c10-math-1371$ ,

(10.7)

Notice that $c10-math-1373$ , and so

because j₁ is chosen to maximize $c10-math-1376$ . Note that among all $c10-math-1377$ , $c10-math-1378$ differ from each other by at most a factor of 2. Therefore, for any $c10-math-1379$ ,

As $c10-math-1381$ , we have $c10-math-1382$ and (10.7) follows.

Now, we let $c10-math-1383$ and take logarithm of both sides of (10.7). We get

Or, $c10-math-1385$ . As Merlin chose z to maximize $c10-math-1387$ , we know that $c10-math-1388$ and $c10-math-1389$ . So, we get $c10-math-1390$ . This completes the proof that system A₂ works correctly when $c10-math-1392$ .

Next, we show that if $c10-math-1393$ , then, with probability at least 3/4, Arthur rejects x. Assume that Arthur does not reject by the end of step (4) of Stage 2. Let y and z be the strings sent by Merlin to Arthur at step (3) of Stage 1, and let $c10-math-1397$ be the sets sent by Arthur to Merlin at step (2) of Stages 1 and 2. Let d be any positive integer. We claim

$c10-math-1399$ , and
$c10-math-1400$ .

To see that (a) holds, we let U_d be the set of all strings u of length q(n) such that $c10-math-1404$ , where v_u is the string of length q(n) that maximizes $c10-math-1407$ (when u and x are fixed). We observe that $c10-math-1410$ because $c10-math-1411$ . As Arthur does not reject at step (4) of Stage 1, we know that $c10-math-1412$ and, hence, by Lemma 10.23(c),

Claim (b) follows similarly from Lemma 10.23(c), noticing that if Arthur does not reject at step (4) of Stage 2, it must be true that $c10-math-1414$ $c10-math-1415$ .

Now, let $c10-math-1416$ . Then, we see that the probability is at least 3/4 such that

It implies that $c10-math-1418$ . Recall that $c10-math-1419$ , and so $c10-math-1420$ . Taking logarithm on both sides, we get $c10-math-1421$ (note that $c10-math-1422$ and, hence, $c10-math-1423$ ).

We have just proved that if Arthur does not reject before step (5) of Stage 2, he would reject at step (5) of Stage 2 with probability at least 3/4. This completes the proof of the correctness of system A₂.

Finally, we observe that the proof system A₂ lasts totally five rounds on any input x. (In general, for k ≥ 2, the system A₂ needs $c10-math-1429$ rounds; see Exercise 10.12.) This shows that $c10-math-1430$ and, hence, in $c10-math-1431$ .

In Chapter 4, we saw some examples of problems that are known to be in NP but are not known to be in P or to be NP-complete. In Examples 10.1 and 10.2, we showed that the complements of two of these problems, GISO and QR, have two-round interactive proof systems. From the above result, we know that the complements of GISO and QR are actually in $c10-math-1432$ and, hence, by Theorem 10.20, GISO and QR cannot be NP-complete unless the polynomial-time hierarchy collapses to the second level. Thus, the study of interactive proof systems yields some surprising results regarding the NP-completeness of some natural problems.

Corollary 10.25

Proof

10.5 IP Versus PSPACE

In the past few sections, we have established that the computational power of the interactive proof systems of a constant number of rounds is quite limited and is just alevel beyond NP. A critical step of this collapsing result is Theorem 10.14, where two complementary $c10-math-1437$ -predicates are converted to two complementary $c10-math-1438$ -predicates. A careful analysis shows that this result cannot be extended to complementary $c10-math-1439$ -predicates if k(n) is not bounded by a constant (cf. Exercise 10.6). Therefore, the collapsing result stops at the constant-round AM hierarchy. Indeed, we show in the following that IP is actually equal to PSPACE, and so any result collapsing IP to the polynomial-time hierarchy would be a major breakthrough.

Theorem 10.26

Proof

First, we show that $c10-math-1442$ . By the Merlin machine characterization of the class AM (Proposition 10.11), we only need to show a polynomial-space-bounded simulation of polynomial-time-bound, probabilistic, nondeterministic machine M.

On an input x of length n, the computation of M on x is a tree of depth p(n) for some polynomial p. Each node of the tree is a configuration c and has a value $c10-math-1451$ . We can simply perform a depth-first traversal of this tree, computing $c10-math-1452$ of each node c from the values of their child nodes. (It is the maximum of the values of the child nodes if it is a nondeterministic node, and it is the average of the values of the child nodes if it is a random node.) It is clear that the simulation uses only polynomial space (cf. Theorem 3.17).

Next, we show that each $c10-math-1454$ has an Arthur–Merlin proof system. Assume that L is accepted by a DTM $c10-math-1456$ in space q(n) for some polynomial q. As proved in Theorem 1.28, we may assume that M always halts on an input of length n in $c10-math-1461$ moves. That is, for any input x of length n, the computation of M on x is a sequenceof $c10-math-1466$ configurations, each of length q(n). The following setup is similar to that in Savitch's theorem (Theorem 1.30). We let $c10-math-1468$ be the predicate stating that the configuration β of M can be reached from the configuration α in exactly k moves. We assume that there is a unique halting configuration α_f of M. Thus, the question of whether $c10-math-1475$ is reduced to the predicate $c10-math-1476$ , where α₀ is the initial configuration of the computation of M on x.

The main idea of the Arthur–Merlin proof system for L is to arithmetize the predicate $c10-math-1481$ into an integer polynomial over $c10-math-1482$ variables. Then Merlin tries to convince Arthur that the polynomial $c10-math-1483$ evaluates to 1 when α is set to α₀ and β is set to α_f. At each stage, Arthur and Merlin work together to reduce the problem of whether a polynomial $c10-math-1488$ evaluates to 1 to the problem of whether some simpler polynomials $c10-math-1489$ evaluate to 1. The reduction is similar to the reduction in the interactive proof system for PERM of Example 10.3.

We first describe the arithmetization of the predicate $c10-math-1490$ . We assume that all configurations α are strings over alphabet $c10-math-1492$ of length exactly q(n). We let α_i denote the ith symbol of α. In the proof of Cook's theorem, we have constructed a Boolean formula ϕ₄ that encodes the predicate $c10-math-1498$ . Let us examine this formula more carefully. Suppose $c10-math-1499$ via an instruction $c10-math-1500$ , where $c10-math-1501$ and $c10-math-1502$ . Then, there must be a position i, $c10-math-1504$ , such that $c10-math-1505$ , $c10-math-1506$ , $c10-math-1507$ , and $c10-math-1508$ for all $c10-math-1509$ and all $c10-math-1510$ . Suppose $c10-math-1511$ via an instruction $c10-math-1512$ . Then, there must be a position i, $c10-math-1514$ , such that $c10-math-1515$ , $c10-math-1516$ , $c10-math-1517$ , and $c10-math-1518$ for all $c10-math-1519$ and all $c10-math-1520$ . Therefore, we may encode $c10-math-1521$ as a formula of the following form:

(10.8) equation

where i^′ (equal to either i + 1 or i − 1), b, and r are to be determined from the instruction $c10-math-1528$ . Notice that in the right-hand side of (10.8), there is at most one nonzero term, because M is deterministic.

Now we use Boolean variables to encode tape symbols. Namely, let α_i,a be the Boolean variable indicating $c10-math-1531$ . Then, each equation of the form $c10-math-1532$ in formula (10.8) becomes the product of k equations $c10-math-1534$ for some constants k, and each equation of the form $c10-math-1536$ becomes equations $c10-math-1537$ and $c10-math-1538$ for all $c10-math-1539$ . Thus, we obtain a Boolean formula $c10-math-1540$ over Boolean variables of the form α_i,a and β_i,a such that it evaluates to 1 with respect to the intended values of α_i,a and β_i,a if and only if $c10-math-1545$ . In addition, $c10-math-1546$ is a sum of the products of the form $c10-math-1547$ or $c10-math-1548$ , where x, y are Boolean variables and c is a Boolean constant. Replacing $c10-math-1552$ by $c10-math-1553$ , we obtain an arithmetic formula $c10-math-1554$ with the following properties:

$c10-math-1555$ if and only if $c10-math-1556$ , when variables α_i,a take the value 1 if $c10-math-1558$ , and 0 if $c10-math-1559$ , and variables β_i,a take the value 1 if $c10-math-1561$ , and 0 if $c10-math-1562$ .
$c10-math-1563$ is multilinear, that is, f₁ has degree 1 in each variable.

The property (i) above follows from the observation that formula ϕ₁ (and, hence, ψ₁) contains at most one nonzero term. It implies that even if we use integer arithmetic instead of Boolean arithmetic, the formula f₁ always evaluates to either 0 or 1 on inputs of values 0 or 1. (It may assume other values if inputs to variables are not limited to 0 or 1.)

Next, for each k > 1, consider the predicate $c10-math-1569$ . It is clear that

Therefore, we just inductively define, for $c10-math-1571$ ,

(10.9) equation

where the summations are taken over all possible variables γ_i,a, for all $c10-math-1574$ and all $c10-math-1575$ . Then, we claim that $c10-math-1576$ is equivalent to $c10-math-1577$ in the sense of property (i) above.

Let us call the assignments of values to variables α_i,a illegal if they do not correspond to a configuration α (e.g., if there exist $c10-math-1580$ , $c10-math-1581$ , such that $c10-math-1582$ for some $c10-math-1583$ ). First, we can prove, by a simple induction, that if the assignments to α_i,a's are legal and the assignments to β_i,a's are illegal, then $c10-math-1586$ . Indeed, for k = 1, this follows from the formula $c10-math-1588$ . For k > 1, $c10-math-1590$ implies for some γ, $c10-math-1592$ and $c10-math-1593$ . So, by the inductive hypothesis, if assignments to α_i,a's are legal, then the assignments to γ_i,a's and to β_i,a's must also be legal.

Next, we check that for any configurations α, β, there is at most one configuration γ such that $c10-math-1600$ and $c10-math-1601$ both hold. Therefore, if all variables α_i,a and β_i,a have legal values, there is at most one nonzero term on the right-hand side of (10.9), corresponding to the legal values of the unique configuration γ and, hence, $c10-math-1605$ has value either 0 or 1. By a simple induction, it is easy to see that $c10-math-1606$ if and only if $c10-math-1607$ . This completes the proof of the claim.

We also observe that for each k ≥ 1, f_k remains a multilinear polynomial. (It may appear that some variables γ_i,a may occur twice in the product $c10-math-1611$ and, hence, the degree of such variables may double. However, we note that γ_i,a is not really a free variable and, hence, has nothing to do with the degree of the function f_k.)

The above completes the arithmetization of the predicate $c10-math-1614$ . Following this arithmetization, we see that Merlin needs to prove that the formula $c10-math-1615$ evaluates to 1. Before we present such a proof system, we first introduce some more notations.

Let $c10-math-1616$ . We note that each function f_k has $c10-math-1618$ variables. In general, we write α or β to denote a vector of $c10-math-1621$ integers (not necessarily 0 or 1) and write $c10-math-1622$ to denote the functionvalue of f_k with $c10-math-1624$ integers from vector α assigned to variables α_i,a and $c10-math-1627$ integers from vector β assigned to variables β_i,a. If $c10-math-1630$ , $c10-math-1631$ , are integer constants and if k > 1, then we write $c10-math-1633$ to denote the function value

(In the above, α and β are two vectors of $c10-math-1637$ integers each and each d_j is a single integer and each e_j is a single variable.) In addition, for constants $c10-math-1640$ and variable x, $c10-math-1642$ denotes the degree-2, univariate polynomial

Our Arthur–Merlin proof system uses the following relations to reduce the evaluation of the polynomial $c10-math-1644$ to the evaluation of polynomials $c10-math-1645$ : For $c10-math-1646$ and $c10-math-1647$ ,

and

Arthur–Merlin Sum Check Proof System for L.

Input: w, $c10-math-1652$ .

Stage 0. Merlin finds a prime number p in the range $c10-math-1654$ . Merlin sends to Arthur the prime p, and Arthur verifies that p is indeed a prime. In the rest of the proof system, the arithmetic is done in the field $c10-math-1657$ . Let $c10-math-1658$ , $c10-math-1659$ , and $c10-math-1660$ . (Merlin needs to convince Arthur that $c10-math-1661$ .)

Stage k, $c10-math-1663$ . Let $c10-math-1664$ . Merlin tries to convince Arthur that $c10-math-1665$ .

Substage $c10-math-1666$ , $c10-math-1667$ . Before this substage, Arthur has already chosen random numbers $c10-math-1668$ from $c10-math-1669$ , and a constant $c10-math-1670$ has been defined. At this substage, Merlin tries to convince Arthur that $c10-math-1671$ (except when i = 1, in which case Merlin needs to prove $c10-math-1673$ ). Merlin sends a degree-2, univariate polynomial $c10-math-1674$ to Arthur, claiming that $c10-math-1675$ . Arthur checks that $c10-math-1676$ (he rejects if this does not hold). Then, Arthur picks a random $c10-math-1677$ and sends it to Merlin. Let $c10-math-1678$ .

Substage $c10-math-1679$ . Merlin needs to convince Arthur that

First, Merlin sends to Arthur a univariate polynomial $c10-math-1681$ of degree at most $c10-math-1682$ , claiming that

(10.10)

where $c10-math-1684$ . (We treat $c10-math-1685$ , and δ as size- $c10-math-1687$ vectors over $c10-math-1688$ and x as a scaler.) Arthur verifies that $c10-math-1690$ . Then, Arthur picks a random $c10-math-1691$ and sends it to Merlin. Let $c10-math-1692$ and reset $c10-math-1693$ and $c10-math-1694$ . Go to Stage k + 1.

Stage $c10-math-1696$ . Arthur finds the polynomial $c10-math-1697$ and verifies that $c10-math-1698$ . He accepts if and only if this equation holds.

To see that this proof system works correctly, we first assume that $c10-math-1699$ . Then, Merlin can simply be honest. That is, at each substage $c10-math-1700$ , $c10-math-1701$ and $c10-math-1702$ , Merlin sends the correct polynomial $c10-math-1703$ to Arthur, and it will pass Arthur's test. At substage $c10-math-1704$ , Merlin also sends the correct polynomial $c10-math-1705$ to Arthur. Note that if h_k satisfies (10.10), then $c10-math-1707$ and $c10-math-1708$ . Thus it also passes Arthur's test at this substage. Furthermore, at the end of each stage k, it remains true that $c10-math-1710$ .In particular, at stage $c10-math-1711$ , Arthur accepts. In other words, if $c10-math-1712$ , then Arthur accepts w with probability 1.

Conversely, if $c10-math-1714$ , we show that the probability of Arthur accepting w is at most 1/4. We first make two critical observations.

Claim 1. If at the start of substage $c10-math-1716$ , for any $c10-math-1717$ and $c10-math-1718$ , $c10-math-1719$ , and if Arthur does not reject in substage $c10-math-1720$ , then by the end of substage $c10-math-1721$ , we have, with probability $c10-math-1722$ , that $c10-math-1723$ .

Proof of Claim 1. If Merlin gives Arthur the correct polynomial $c10-math-1724$ as $c10-math-1725$ , then it cannot pass Arthur's test, because

Therefore, Merlin must have given Arthur a polynomial $c10-math-1727$ that is different from the polynomial $c10-math-1728$ . As both of these polynomials are polynomials of degree 2, they agree at most at two points. That is, the probability that they agree at a random point $c10-math-1729$ is $c10-math-1730$ . So, with probability $c10-math-1731$ , $c10-math-1732$ is not equal to $c10-math-1733$ .

Claim 2. If at the start of substage $c10-math-1734$ , for any $c10-math-1735$ , $c10-math-1736$ , and if Arthur does not reject in substage $c10-math-1737$ , then by theend of substage $c10-math-1738$ , we have, with probability $c10-math-1739$ , that $c10-math-1740$ .

Proof of Claim 2. It is similar to Claim 1, except here the polynomial $c10-math-1741$ has degree at most $c10-math-1742$ and so the probability of $c10-math-1743$ is at most $c10-math-1744$ .

Now, if this proof system is given an input $c10-math-1745$ , then it begins with $c10-math-1746$ . Suppose Arthur does not reject in the first q(n) stages; then, by the above claims, we have, by Stage $c10-math-1748$ , probability at least $c10-math-1749$ (for sufficiently large n) that $c10-math-1751$ , and Arthur will reject it at Stage $c10-math-1752$ . This completes the proof of the correctness of the Arthur–Merlin proof system for L.

Finally, we note that in each substage, Arthur's task is only to evaluate a polynomial of degree at most $c10-math-1754$ in the field $c10-math-1755$ , with $c10-math-1756$ . This can be done in polynomial time. Furthermore, there are only $c10-math-1757$ substages. Therefore, the whole proof system operates in polynomial time.

We remark that the above proof also establishes Theorem 10.22. In particular, the above sum check proof system has only a one-sided error.

In Chapter 4, we mentioned that most results that separate complexity classes by the diagonalization techniques or collapsing complexity classes by the simulation techniques are relativizable, that is, these results hold relative to all oracles (if the relativized complexity classes can be defined in a natural way). It is, therefore, interesting to point out here that the above result of $c10-math-1758$ is not relativizable. (Exercise 10.13 constructs an oracle A such that $c10-math-1760$ .) Thus, this algebraic proof technique may potentially lead to more separating or collapsing results that are not provable by the standard diagonalization or the simulation techniques.

Exercises

10.1In this exercise, we present a balanced view of the interactive proof systems (in contrast to the verifier's view of the interactive proof systems defined in Definition 10.5). We define an interactive protocol as a pair of machines $c10-math-1761$ , where M_v is a polynomial-time PTM, M_p is a DTM, and they share a common read-only input tape and a common communication tape. The two machines take turns in being active. During its active stage, the machine (except for the first stage) first reads the string in the communication tape, performs some local computation on its local tapes, and then writes a string on the communication tape (or if the machine is M_v, it may choose to halt the computation and accept or reject). We say a set $c10-math-1765$ has an interactive proof system with error bound ε if there exists a polynomial-time PTM M_v such that the following hold:

There exists a DTM M_p such that $c10-math-1769$ is an interactive protocol and for each $c10-math-1770$ , the probability of M_v and M_p together accepting x is at least $c10-math-1774$ ; and
For any DTM M such that $c10-math-1776$ forms an interactive protocol and for any $c10-math-1777$ , the probability of M_v and M together accepting x is at most ε.

Show that the above definition of interactive proof systems is equivalent to Definition 10.5.

10.2Assume that A has a k(n)-round interactive proof system $c10-math-1784$ with the error probability $c10-math-1785$ . Further assume that in the system $c10-math-1786$ , each message exchanged between the prover and the verifier is of length at most q(n) and the machine M_v uses at most r(n) random bits, if the input is of length n. Prove that for any polynomial p, there is a k(n)-round interactive proof system for A with the error probability $c10-math-1794$ , in which the message length is bounded by $c10-math-1795$ and the number of random bits used is bounded by $c10-math-1796$ . In particular, for any m > 0, there is a k(n)-round interactive proof system $c10-math-1799$ for A with the error probability $c10-math-1801$ , where $c10-math-1802$ is the number of random bits used by $c10-math-1803$ .

10.3It is shown through Theorem 10.24 that the problem $c10-math-1804$ is in $c10-math-1805$ . Give a direct proof for this fact by demonstrating an Arthur–Merlin proof system for $c10-math-1806$ . [Hint: Let $c10-math-1807$ be a graph and $c10-math-1808$ be a permutation of the vertices of G. We write $c10-math-1810$ to denote the graph $c10-math-1811$ , where $c10-math-1812$ if and only if $c10-math-1813$ . Let $c10-math-1814$ be the set of all automorphisms of G, that is, the set of all permutations π over V such that $c10-math-1818$ is identical to G. We observe that in the interactive proof system of Example 10.1, if the inputs G₁ and G₂ are isomorphic, then there are only $c10-math-1822$ different messages that could be sent by the verifier to the prover in round 1 (called legal messages). Otherwise, if G₁ and G₂ are not isomorphic, then there are $c10-math-1825$ different legal messages. Design an Arthur–Merlin proof system for $c10-math-1826$ in which Merlin tries to convince Arthur that there are “many” legal messages for the given inputs G₁ and G₂.]

10.4Design an interactive proof system for $c10-math-1829$ .

10.5There is a natural extension of Merlin machines to oracle Merlin machines in which Merlin can make queries to an oracle X. Define the notion of relativized $c10-math-1831$ based on oracle Merlin machines.

Show that the class $c10-math-1832$ has an alternating quantifier characterization like that of Theorem 10.15.
Prove that $c10-math-1833$ .

10.6It is straightforward to extend the notion of complementary $c10-math-1834$ -predicates to complementary $c10-math-1835$ -predicates, where k(n) is a function of the input n.

Can you prove an alternating quantifier characterization for $c10-math-1838$ by the notion of complementary $c10-math-1839$ -predicates? If so, what is the best bound for the probability c you can prove?
Assume that R₁ and R₀ are twocomplementary $c10-math-1843$ -predicates, with $c10-math-1844$ for some polynomial p. Show that R₁ and R₀ are two complementary $c10-math-1848$ -predicates. Can you generalize this result to show that R₁ and R₀ are two complementary $c10-math-1851$ -predicates (if necessary, assuming a smaller c₁ to begin with)?

10.7Show that $c10-math-1853$ .

10.8Recall that almost-P denotes the class of languages A such that $c10-math-1855$ (see Exercise 8.16). Extend this notion to almost-NP $c10-math-1856$ . Show that almost- $c10-math-1857$ .

10.9Prove that $c10-math-1858$ . Are these three classes equal?

10.10Prove that if $c10-math-1859$ , then $c10-math-1860$ .

10.11Prove that for each of the following statements, there is an oracle X relative to which the statement is false.

$c10-math-1862$ .
$c10-math-1863$ .
$c10-math-1864$ .

10.12Extend the Arthur–Merlin proof system A₂ of Theorem 10.24 to work for every k ≥ 1. In particular, for any $c10-math-1867$ , find a $c10-math-1868$ -round Arthur–Merlin proof system for L.

10.13Prove that there exists an oracle A such that $c10-math-1871$ .

10.14Prove that if f(n) and g(n) are two functions bounded by some polynomial functions such that $c10-math-1874$ , then there exists an oracle A such that $c10-math-1876$ , where $c10-math-1877$ is the class of sets in PSPACE that have the form (3.7) in Corollary 3.20, with g(n) levels of quantifiers, beginning with $c10-math-1880$ , and $c10-math-1881$ is this class relative to set A.

The following three problems are about zero-knowledge proof systems. Intuitively, a proof session of an interactive proof system provides zero knowledge if the prover is able to convince the verifier that an input x is in the set L and yet the verifier learns no extra knowledge other than the fact that $c10-math-1885$ . For instance, consider the graph isomorphism problem GISO. For two given graphs $c10-math-1886$ and $c10-math-1887$ , a simple proof system is to let the prover send a mapping $c10-math-1888$ to the verifier and let the verifier check that π is an isomorphism between the two graphs. This proof system, however, reveals exactly what the isomorphism is between G₁ and G₂. Alternatively, the following proof system for GISO does not reveal this information and yet can convince the verifier that $c10-math-1892$ : The prover first sends a graph $c10-math-1893$ that is isomorphic to G₁ (and G₂) to the verifier. Then, the verifier picks a random number $c10-math-1896$ and sends it to the prover. The prover sends a function $c10-math-1897$ that is an isomorphism between G_i and G₃. Note that although the verifier learns the isomorphism function between G_i and G₃, he/she is not able to find the isomorphism between G₁ and G₂ from this side knowledge.

We are going to define the notion of zero-knowledge proof systems based on the balanced view of interactive proof systems defined in Exercise 10.1. Recall that on an input x and for a sequence α of random bits, a k-round interactive proof system $c10-math-1907$ has a unique history $c10-math-1908$ (see the proof of Theorem 10.21). Here, we modify it and attach α itself to the history and define $c10-math-1910$ . We notice that for a fixed prover machine M_p, an interactive protocol $c10-math-1912$ defines, for each input x, a probability distribution $c10-math-1914$ on the histories h_x,α. We say a PTM M on input x generates a probability distribution $c10-math-1918$ if for each string w, the probability of M(x) prints w is $c10-math-1922$ . Formally, we define that an interactive proof system $c10-math-1923$ for set L is a perfect zero-knowledge proof system for M_v, if there exists a polynomial-time PTM M that on each input x generates a probabilistic distribution $c10-math-1928$ that is identical to $c10-math-1929$ . We say $c10-math-1930$ is a perfect zero-knowledge proof system, if for every verifier machine $c10-math-1931$ that forms an interactive protocol with M_p, there exists a polynomial-time PTM M that on each input x generates a probabilistic distribution $c10-math-1935$ that is identical to $c10-math-1936$ .

10.15Prove that the above second interactive protocol for GISO is a perfect zero-knowledge proof system.

10.16The interactive protocol for $c10-math-1937$ of Example 10.1 is not perfect zero-knowledge, because a verifier $c10-math-1938$ may send a graph G^′ to the prover that is not randomly generated from G₁ or G₂ and gain information of whether G^′ is isomorphic to G₁ or G₂. Modify this interactive protocol to a perfect zero-knowledge proof system for $c10-math-1945$ .

10.17Prove that if a set L has a perfect zero-knowledge proof system, then $c10-math-1947$ .

If you are going to do something wrong,at least enjoy it.

—Leo Rosten

Historical Notes

Interactive proof systems were first introduced by Goldwasser, Micali, and Rackoff (1989). Their formulation is close to the one presented in Exercise 10.1. Our equivalent formulation is based on the work of Fortnow et al. (1994). Arthur–Merlin proof systems were introduced by Babai (1985) and Babai and Moran (1988) from a different motivation. A number of survey papers have been written about the properties and applications of these proof systems, including Johnson (1988, 1992). Example 10.1 is from Goldreich et al. (1991), and Example 10.3 is from Lund et al. (1992). The robustness of the notion of complementary AM_k-predicates and the collapsing of the AM hierarchy are contained in Babai and Moran (1988). Theorem 10.20 was first proved by Boppana et al. (1987). The equivalence between IP_k and AM_k was first proved by Goldwasser and Sipser (1989). The simpler proof of the weaker form of the equivalence presented in Theorem 10.21 is due to Killian (see Goldwasser (1988)). The notion of universal hashing functions as that used in Lemma 10.23 was first defined by Carter and Wegman (1979). The interactive proof system for the problem $c10-math-1951$ was first presented by Goldreich et al. (1991). Schöning (1987) contains a direct construction of an Arthur–Merlin proof system for the graph nonisomorphism problem (Exercise 10.3). The equivalence of IP and PSPACE was first proved byShamir (1990), based on the idea of Lund et al. (1992). Both proofs worked on the PSPACE-complete problem QBF. Our proof of Theorem 10.26 was based on the unpublished idea of Hartmanis (1991). The characterization of AM as almost-NP (Exercise 10.8) is from Nisan and Wigderson (1994). Exercise 10.14 is from Fortnow and Sipser (1988) and Aiello et al. (1990). Exercise 10.9 is from Goldreich and Zuckerman (1997) and Arvind and Köbler (1997). Zero-knowledge proof systems were first introduced inGoldwasser, Micali, and Rackoff (1989). Exercises 10.15 and 10.16 are from Goldreich et al. (1991). Exercise 10.17 is from Fortnow (1989) and Aiello and Hastad (1991). Goldreich (1997) contains a recent survey on zero-knowledge proof systems.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 10.5

Create new playlist

Sign In

Sign Up

Theorem 10.24

Proof

Corollary 10.25

Proof

10.5 IP Versus PSPACE

Theorem 10.26

Proof

Exercises

Historical Notes

Table of Contents for
10.5