Interactive Proof Systems and Public Coins

Fix $p$ with $\max \{s,1-c,0\}<p<1\mathrm{/}2$. On a yes-input, use one honest strategy afresh in each repetition, ignoring previous copies. Let $Y_i$ indicate rejection in copy $i$. On a no-input, fix any adaptive cheating strategy and instead let $Y_i$ indicate acceptance. In both cases, conditional on the full history of earlier copies, $\mathrm{Pr}(Y_i=1\mid \text{history})\le p$: on yes-inputs this is completeness, and on no-inputs the previous history fixes a legitimate strategy for the next fresh-coin copy, so soundness applies. The verifier is reset between copies.

Put $t=1\mathrm{/}(2p)>1$. If the conditional success probability of $Y_i$ is $u\le p$, then the conditional average of $t^{2Y_i}$ is $1-u+u{t}^2\le 1-p+p{t}^2$. Grouping finite sums by complete previous-copy histories and inducting on $j$ therefore gives $\mathbb{E}[t^{2{\sum }_{i=1}^j{Y}_i}]\le (1-p+p{t}^2{)}^j$, starting with expectation one at $j=0$. This argument allows dependence between copies.

On ${\sum }_{i=1}^k{Y}_i\ge k\mathrm{/}2$ one has $t^{2{\sum }_i{Y}_i}\ge t^k$. Summing this pointwise bound over the finite coin space gives $\mathrm{Pr}({\sum }_i{Y}_i\ge k\mathrm{/}2)\le q^k$, where $q=(1-p+p{t}^2)\mathrm{/}t=1\mathrm{/}2+2p(1-p)=1-2(1\mathrm{/}2-p{)}^2$ satisfies $0<q<1$. For odd $k$, either a majority rejection on a yes-input or a majority acceptance on a no-input is contained in this event.

Write $d=q^{-1}-1>0$. Induction using $(1+d{)}^{k+1}\ge (1+kd)(1+d)\ge 1+(k+1)d$ gives $q^k\le 1\mathrm{/}(1+kd)$. Choose an odd integer $k$ making this at most $\epsilon$. For fixed $c,s,\epsilon$ it is a constant independent of input length, so the repeated verifier retains polynomial time, communication and randomness bounds. The yes-input honest strategy and the uniform bound against every no-input cheating strategy give the two asserted errors.

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.

Write $N={\sum }_{z\in S}{I}_z$, where $I_z$ indicates $h(z)=y$. Summing the assumed joint probabilities over outputs at any distinct input gives $\mathbb{E}{I}_z=1\mathrm{/}\mathrm{\mid }R\mathrm{\mid }$. For distinct $z,z^{\mathrm{\prime }}$, $\mathbb{E}(I_z{I}_{z^{\mathrm{\prime }}})=\mathrm{\mid }R{\mathrm{\mid }}^{-2}$, so their covariance is zero by expansion of its defining finite sum.

Interchanging finite sums gives $\mathbb{E}N=\mathrm{\mid }S\mathrm{\mid }\mathrm{/}\mathrm{\mid }R\mathrm{\mid }$. Expanding $(N-\mathbb{E}N{)}^2$ and using the zero cross terms gives $\mathrm{Var}N={\sum }_z\mathrm{Var}{I}_z$. Since $I_z^2=I_z$, each summand is $\mathrm{\mid }R{\mathrm{\mid }}^{-1}(1-\mathrm{\mid }R{\mathrm{\mid }}^{-1})$. Thus $\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 $\tau$, let $C(\tau )$ be the set of all length-$r$ tapes consistent with the verifier messages in $\tau$ when it is fed the prover messages recorded there. Enumerate tapes and simulate the verifier to test this condition, without storing $C(\tau )$. A deterministic strategy choosing the recorded prover messages gives every tape in $C(\tau )$ 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(\tau )$, the maximum number of tapes in $C(\tau )$ accepted by a single continuation strategy based on public transcripts. If $C(\tau )$ is empty, put $W(\tau )=0$ and do not recurse. At a terminal node count the accepting compatible tapes. At a verifier node the sets $C(\tau m)$, for distinct next public messages $m$, partition $C(\tau )$, so put $W(\tau )={\sum }_{m}W(\tau m)$. At a prover node, appending its response $m$ does not filter the compatible tapes, so put $W(\tau )={\max }_{m}W(\tau m)$. 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(\tau )$ the conditional value is $W(\tau )\mathrm{/}\mathrm{\mid }C(\tau )\mathrm{\mid }$. At verifier nodes this is exactly the weighted average of child values, since each weight is $\mathrm{\mid }C(\tau m)\mathrm{\mid }\mathrm{/}\mathrm{\mid }C(\tau )\mathrm{\mid }$; at prover nodes the common denominator makes maximizing the numerator equivalent to maximizing the value. Moreover $0\le W(\tau )\le \mathrm{\mid }C(\tau )\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$ and all input cells. This deterministic decider places $L_V$ in PSPACE by The classes DTIME, NTIME, DSPACE, and NSPACE, 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$.

Using adjacency-matrix graph encodings, the verifier first checks the two encoded inputs are graphs, rejecting malformed inputs. If their vertex counts differ, it accepts: such graphs cannot be isomorphic. Both checks are deterministic polynomial-time. In the remaining case relabel both vertex sets as $\{1,\dots ,n\}$ and use the bounded-rejection protocol The graph-nonisomorphism interactive protocol. Its factorial arithmetic and four bounded draws meet the verifier's worst-case polynomial time and random-bit budget. If $G_0\cong ̸G_1$, every permutation, including the fallback identity, leaves $H$ in exactly one of the two isomorphism classes, so an unbounded prover answers correctly with probability $1$.

If $G_0\cong G_1$, the successful-draw branch gives the same uniform distribution $U$ of $H$ for both values of $b$. The fallback has probability $\epsilon <1\mathrm{/}16$ and gives $H=G_b$, so the two challenge distributions are $(1-\epsilon )U+\epsilon {\delta }_{G_0}$ and $(1-\epsilon )U+\epsilon {\delta }_{G_1}$. Their total-variation distance is at most $\epsilon$. With a uniform hidden bit $b$, any prover's best guess from $H$ has success probability at most $(1+\epsilon )\mathrm{/}2<17\mathrm{/}32$; this follows directly by summing, for each possible $H$, the larger of its two joint probabilities.

Run two fresh independent challenges and accept only when both answers are correct. On a no instance, after every first transcript the second challenge still has fresh private coins, so even an adaptive prover has conditional success probability below $17\mathrm{/}32$. Thus two-copy soundness is below $(17\mathrm{/}32{)}^2=289\mathrm{/}1024<1\mathrm{/}3$, while completeness remains $1$. The two copies retain a fixed polynomial worst-case budget, so 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.