Interactive Proof Systems and Public Coins

By The class NP via polynomial-time verifiers, on input $x$ the prover may send a polynomially bounded certificate $w$, and the verifier can test it in polynomial time.

If $x\in L$, some $w$ is accepted, whereas if $x\mathrm{\notin }L$, no $w$ is accepted. This is a one-round protocol with completeness $1$ and soundness $0$, hence is an IP protocol by The class IP.

For the honest prover, the acceptance indicators are independent Bernoulli variables of mean at least $c$; the lower-tail Chernoff bound A Chernoff bound for sums of independent Bernoulli trials, applied to these success indicators, makes majority failure exponentially small in the number $k$ of copies.

Against any adaptive prover, conditional on every earlier transcript, the next copy accepts with probability at most $s$ by Completeness and soundness of an interactive protocol. Induction on copies gives $\mathbb{E}{e}^{\lambda \sum X_i}\le (1-s+s{e}^{\lambda }{)}^k$, so the usual Chernoff upper-tail calculation makes majority acceptance exponentially small.

Choose odd $k$ large enough that both exponential bounds are at most $\epsilon$; for fixed $c,s,\epsilon$ this is constant and preserves polynomial bounds.

Write $N={\sum }_{z\in S}{I}_z$, where $I_z$ indicates $h(z)=y$. Since $\mathrm{\mid }U\mathrm{\mid }\ge 2$, the pairwise-independence definition Pairwise independent hash families gives uniform marginals by summing the joint distribution over a distinct input; it also gives zero covariances for distinct $z$. Thus $\mathbb{E}{I}_z=1\mathrm{/}\mathrm{\mid }R\mathrm{\mid }$.

Hence $\mathbb{E}N=\mathrm{\mid }S\mathrm{\mid }\mathrm{/}\mathrm{\mid }R\mathrm{\mid }$ and $\mathrm{Var}N={\sum }_z\mathrm{Var}{I}_z\le {\sum }_z\mathbb{E}{I}_z=\mathbb{E}N$. More exactly, $\mathrm{Var}N=\mu (1-1\mathrm{/}\mathrm{\mid }R\mathrm{\mid })\le \mu$.

Since $N$ is a nonnegative integer, ${\mathbf{1}}_{\{N>0\}}\le N$, so $\mathrm{Pr}(N>0)\le \mu \le 1\mathrm{/}4$ in the small regime. For $\mu >0$, on $N=0$ one has $(N-\mu {)}^2={\mu }^2$, hence ${\mu }^2\mathrm{Pr}(N=0)\le \mathbb{E}(N-\mu {)}^2\le \mu$. Therefore $\mathrm{Pr}(N>0)\ge 1-1\mathrm{/}\mu \ge 3\mathrm{/}4$ when $\mu \ge 4$.

If $N=0$, no prover response passes the stated checks. If $N>0$, an unrestricted prover can supply a valid preimage. Thus the optimal acceptance probability is exactly $\mathrm{Pr}(N>0)$. The checks are polynomial-time under the stated encoding and algorithmic hypotheses, and revealing every sampling bit before the response makes the protocol public-coin. This proves the quantitative challenge claim.

The Goldwasser--Sipser conversion replaces the hidden continuation at each verifier move by a public set-lower-bound subprotocol: Arthur announces a pairwise-independent hash and Merlin supplies a compatible accepting continuation in the announced hash fibre. The fibre estimate of Pairwise-independent hashing controls fibre size is the variance calculation used by that subprotocol.

Arora--Barak's stated public-coin conversion establishes $\mathrm{I}\mathrm{P}[k]\subseteq \mathrm{A}\mathrm{M}[k+2]$ for every polynomial-time computable round bound $k$. Its construction has polynomial-length hashes, challenges, and witnesses, hence preserves polynomial verification and produces a public-coin protocol for the same language.

A public-coin verifier is already a private-coin verifier which reveals its coins. Therefore both inclusions hold.

At each prover node, the finitely many child values have a maximum; choose one maximizing child.

Backward induction from terminal nodes shows that the choices in step 1.1 attain the value at every prover node, while random nodes retain their prescribed averages. By Protocol game trees and their values, the resulting deterministic strategy attains the root value.

Pad its random tape to $r=r(\mathrm{\mid }x\mathrm{\mid })$ fair bits. For a public transcript $au$, let $C(au)$ be the set of all length-$r$ tapes consistent with the verifier messages in $au$ when it is fed the prover messages recorded there. Enumerate tapes and simulate the verifier to test this condition, without storing $C(au)$. A deterministic strategy choosing the recorded prover messages gives every tape in $C(au)$ the same conditional weight. This is the private-history distribution of Protocol game trees and their values. Terminal values average over all compatible tapes. Variable stopping times can be handled by a public termination marker and dummy exchanges after termination, retaining the original accept/reject outcome.

Compute an integer $W(au)$, the maximum number of tapes in $C(au)$ accepted by a single continuation strategy based on public transcripts. If $C(au)$ is empty, put $W(au)=0$ and do not recurse. At a terminal node count the accepting compatible tapes. At a verifier node the sets $C(aum)$, for distinct next public messages $m$, partition $C(au)$, so put $W(au)=su{m}_{m}W(aum)$. At a prover node, appending its response $m$ does not filter the compatible tapes, so put $W(au)=ma{x}_{m}W(aum)$. Enumerate all bounded message strings; invalid responses cause rejection. Strategies in distinct public-message children can be combined because the prover sees which child occurred. At a prover node the same response serves every compatible hidden history. Backward induction, also justified by An optimal prover may be deterministic, therefore gives the intended maximum.

For nonempty $C(au)$ the conditional value is $W(au)\mathrm{/}\mathrm{\mid }C(au)\mathrm{\mid }$. At verifier nodes this is exactly the weighted average of child values, since each weight is $\mathrm{\mid }C(aum)\mathrm{\mid }\mathrm{/}\mathrm{\mid }C(au)\mathrm{\mid }$; at prover nodes the common denominator makes maximizing the numerator equivalent to maximizing the value. Moreover $0leW(au)le\mathrm{\mid }C(au)\mathrm{\mid }le{2}^r$. Each running sum, maximum, count and message or tape index therefore has polynomial bit length. A depth-first evaluation retains polynomial space per frame and has polynomially many frames; verifier simulations take polynomial space and siblings are recomputed. Thus $A(x)=W(\mathrm{\varnothing })$ is computable in polynomial space and $\mathrm{\mid }C(\mathrm{\varnothing })\mathrm{\mid }=2^r$. This includes $r=0$, whose tape set consists of the empty string.

Output $A(x)$ and $2^r$ in binary, without needing to reduce the fraction. For a well-formed threshold input, compute $A(x)$ and decide $A(x)b>a{2}^r$ by integer arithmetic. Its space is polynomial in the total input length, including the bit lengths of $a,b$. This deterministic decider places $L_V$ in PSPACE by The classes PSPACE and NPSPACE, while the binary-pair output establishes the claimed exact function computation.

On input $x$, compute the public-information protocol root value in polynomial space. The prover maxima are indexed by public transcripts, while verifier randomness is averaged over the compatible private histories, so this is the value of a legal prover strategy rather than a full-information strategy.

Accept precisely when that value exceeds $1\mathrm{/}2$. It is at least $2\mathrm{/}3$ on $x\in L$ and at most $1\mathrm{/}3$ on $x\mathrm{\notin }L$, so this test decides $L$.

If $G_0\cong ̸G_1$, the isomorphism class of $H$ identifies the unique $b$, so an unbounded prover answers correctly with probability $1$.

If $G_0\cong G_1$, the distributions of $\pi (G_0)$ and $\pi (G_1)$ are identical; even conditioned on $H$, $b$ is uniform, so every prover succeeds with probability $1\mathrm{/}2$. This verifies the protocol The graph-nonisomorphism interactive protocol.

Run two fresh independent challenges and accept only when both answers are correct. On a no instance, after every first transcript the second challenge is still independent and every response succeeds with conditional probability at most $1\mathrm{/}2$; thus the two-copy soundness is at most $(1\mathrm{/}2{)}^2=1\mathrm{/}4$, while completeness remains $1$. Hence The class IP applies.

The honest prover is selected to establish completeness on yes instances; on a no instance it is not an adversarial model.

By Completeness and soundness of an interactive protocol, soundness requires the acceptance bound for every prover strategy on every no input. Restricting it to an honest strategy changes the definition and cannot protect against cheating, so the statement is false.

The verifier's polynomial running time bounds each message length and the number of rounds.

A prover strategy in Interactive-proof transcripts, rounds, and prover strategies is an arbitrary response function, explicitly with no computability or time restriction. Therefore the asserted requirement is false.