IPPSPACE

IPPSPACE is a complexity-theoretic class defined in the area of interactive proofs. It refers to languages that admit an interactive proof system in which the verifier is restricted to polynomial space (PSPACE) in the input length. In such a system, a computationally unbounded prover interacts with the PSPACE-bounded verifier to convince the verifier that a given string belongs to the language. The standard completeness and soundness requirements apply: for strings in the language there exists a prover strategy that makes the verifier accept with high probability, and for strings not in the language no prover strategy can force acceptance with probability beyond a specified bound.

The resource constraint on the verifier is central: the verifier’s work is limited to polynomial space, and rounds and message lengths are typically bounded so that the interaction remains space-bounded. Because the verifier’s space is limited, the overall protocol is analyzed with respect to how much space the verifier consumes during the interaction.

Relationship to other classes varies with definitions. It is straightforward to see that PSPACE ⊆ IPPSPACE, since any PSPACE language can be decided by a PSPACE verifier without relying on the prover. IPPSPACE is also known to be contained in EXP, since a PSPACE verifier and any interaction can be simulated by an exponential-time machine. In many treatments, IP equals PSPACE, and as a consequence languages with PSPACE-bounded interactive proofs relate to the broader IP/PSPACE landscape; however, the exact inclusions can depend on the precise formalization of the verifier, rounds, and message lengths.

Examples of PSPACE-complete problems, such as TQBF, are encompassed by IPPSPACE. See also interactive proofs, PSPACE, IP, and MIP for related topics.