Interactive proof system

An interactive proof system is a concept from complexity theory. This is an abstract machine, in which the information processing is realized by the exchange of messages is described. An interactive proof system must satisfy the Completeness and Soundness condition.

They were introduced in 1985 by Shafi Goldwasser, Silvio Micali, Charles Rackoff and (where Preprints up to 1982 declined ) and independent of Laszlo Babai 1985 which details published on this later with Shlomo Moran. The authors obtained for the first Gödel Prize in 1993.

Formally

An interactive proof system ( IBS) is a protocol between proof guide ( prover ) and an investigator ( Verifier ). Here is a PSPACE machine and a randomized Turing machine with polynomial time bound. Submitting evidence and investigators are given the same input on a read-only tape. The protocol includes polynomially many rounds in which only polynomially many messages can be replaced. accepted in the final round or discards the examiner (yes / no or 1/ 0).

A decides a language if for all inputs:

Example

Input: Two graphs

It is notoriously difficult to know whether two graphs are isomorphic (see isomorphism of graphs ). If and are isomorphic, so Merlin can not decide which origin.

The basic idea

The evidence with Merlin wants the auditor King Arthur prove a statement. Arthur, however, is limited in its capacity and therefore can not follow Merlin's evidence as a whole. That is why Merlin Arthur tries to serve the evidence in small bites, which can calculate Arthur for themselves. The evidence guide ( Merlin ) is a PSPACE machine, the auditor ( Arthur) is P- limited. The example was described by László Babai first.

Complexity class

For the complexity class IP that contains all decision problems that have an interactive proof system, then: IP = PSPACE