Interactive evidence system

An interactive proof system is a term from complexity theory . An abstract machine in which information processing is implemented through the exchange of messages is described. An interactive evidence system must meet the completeness and soundness condition.

They were introduced in 1985 by Shafi Goldwasser , Charles Rackoff and Silvio Micali (with preprints going back to 1982) and independently of László Babai in 1985, who later published about them in detail with Shlomo Moran . The authors received the first Gödel Prize for this in 1993.

Formally

An Interactive Evidence System (IBS) is a protocol between a prover and a verifier. There is a PSPACE machine and a probabilistic Turing machine with a polynomial time limit . Evidence and examiner receive the same input on a read-only tape. The protocol includes many polynomial rounds in which only a large number of polynomial messages may be exchanged. in the last round the examiner then accepts or rejects (yes / no or 1/0). ${\displaystyle (P,V)}$ ${\displaystyle P}$ ${\displaystyle V}$ ${\displaystyle x,|x|=n,}$ ${\displaystyle p(n)}$ ${\displaystyle (P,V)=(p_{1},v_{1},p_{2},v_{2},...,p_{p(n)},v_{p(n)})}$

One decides a language if the following applies to all entries : ${\displaystyle \mathrm {IBS} (P,V)}$ ${\displaystyle L\subseteq \Sigma ^{*}}$ ${\displaystyle x\in \Sigma ^{*}}$

1. Is so the examiner accepted with probability ${\displaystyle x\in L}$ ${\displaystyle P(x\in L)\leq (1-2^{-n})}$
2. If so, there is no such thing as a probability that the examiner will accept. ${\displaystyle x\notin L}$ ${\displaystyle \mathrm {IBS} (P,V)}$ ${\displaystyle P(x\in L)>2^{-n}}$

example

Input: two graphs ${\displaystyle G_{1},G_{2}}$

1. Arthur begins: He randomly selects one of the two graphs ( or ) and permutes the naming of the nodes to a new, isomorphic graph . He transmits this graph to Merlin. ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle H}$
2. Merlin calculates back the permutations of and can thus decide whether Arthur originally selected Graph or . Merlin then sends the number of the graph (1,2) to Arthur. ${\displaystyle H}$ ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$
3. Arthur accepts if Merlin sends the correct number.

It is known to be difficult to find out whether two graphs are isomorphic ( see Isomorphism of Graphs ). If and are isomorphic, Merlin cannot decide which origin has. ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle H}$

Basic idea

Evidence leader Merlin wants to prove a statement to the examiner King Arthur . Arthur, however, is limited in terms of his receptivity and therefore cannot follow Merlin's proof as a whole. Therefore Merlin tries to serve Arthur the proof in small bites, which Arthur can work out for himself. The evidencer (Merlin) is a PSPACE machine, the examiner (Arthur) is P -constraint. The example was first described by László Babai .

Complexity class

For the complexity class IP , which contains all decision problems that an interactive proof system possesses, the following applies: IP = PSPACE

Individual evidence

1. ↑ ^{a b} Fourer et al. On Completeness and Soundness in Interactive Proof Systems On Completeness and Soundness in Interactive Proof Systems Advances in Computing Research 1989
2. ↑ Babai, Moran: Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes , Journal of Computer and System Sciences, Volume 36, 1988, pages 254-276
3. ↑ Shafi Goldwasser, Silvio Micali, Charles Rackoff The knowledge complexity of interactive proof systems The knowledge complexity of interactive proof systems SIAM Journal on Computing. 1989
4. ↑ László Babai. Trading group theory for randomness . Proceedings of the Seventeenth Annual Symposium on the Theory of Computing , ACM. 1985.