Math 2.0

Computer science Definition

Interactive proof system

Builds on Probabilistic Turing machineFormal languageComplexity class

Definition

A verifier is a probabilistic Turing machine VV that, on input xx, exchanges messages with a prover PP. The prover is an arbitrary function from the input and the messages so far to the next message. Both see the input xx; only VV sees its own random bits. After the exchange VV outputs accept or reject. Let L⊆{0,1}∗L \subseteq \set{0,1}^* be a language. An interactive proof system for LL is a verifier VV together with a polynomial qq such that:

  1. on every input xx, the exchange has at most q(∣x∣)q(\abs{x}) messages and VV runs in at most q(∣x∣)q(\abs{x}) steps in total, whatever the prover does;
  2. (completeness) there is a prover PP such that for every x∈Lx \in L, VV accepts with probability at least 2/32/3 when interacting with PP;
  3. (soundness) for every x∉Lx \notin L and every prover P∗P^*, VV accepts with probability at most 1/31/3 when interacting with P∗P^*.

The class IP is the class of languages that have an interactive proof system.

Remarks

Example: graph non-isomorphism. On input two graphs G0,G1G_0, G_1 on nn vertices, VV picks a uniform bit bb and a uniform permutation π\pi of the vertices. It sends the graph π(Gb)\pi(G_b) and asks the prover for bb. This is done twice, and VV accepts if both answers are right. If G0G_0 and G1G_1 are not isomorphic, an all-powerful prover finds bb from π(Gb)\pi(G_b) and VV always accepts. If they are isomorphic, π(Gb)\pi(G_b) has the same distribution for b=0b = 0 and b=1b = 1, so any prover is right in each round with probability 1/21/2, and VV accepts with probability 1/41/4.

Non-example: a verifier that accepts whenever the prover sends the message "yes" fails clause 3 for every x∉Lx \notin L, since a cheating prover sends "yes".

If VV uses no random bits, the prover can compute all of VV's messages in advance, and the protocol amounts to a single certificate. Such systems give exactly the class NP. Constants 2/32/3 and 1/31/3 can be replaced by 1−2−∣x∣1 - 2^{-\abs{x}} and 2−∣x∣2^{-\abs{x}} by repetition. If the verifier's random bits are public, the protocol is an Arthur–Merlin protocol.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph
Complexity class, concept, no evidence levelComplexity classconceptFormal language, concept, no evidence levelFormal languageconceptProbabilistic Turing machine, concept, no evidence levelProbabilistic Turing …conceptInteractive proof system, definition, no evidence levelInteractive proof sys…definition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Complexity class concept
  2. Formal language concept
  3. Probabilistic Turing machine concept
  4. Interactive proof system definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Interactive_proof_system
About this page
TagFRP6TPF0SV
URIm2://FRP6TPF0SV
Kinddefinition
WritingW0 stub
MSC68Q10, 68Q15, 68Q87
DefinesInteractive proof system
UsesProbabilistic Turing machine, Formal language, Complexity class
Changed3 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.