A polynomial-round protocol value is computable in polynomial space

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.