In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
, the class IP (interactive polynomial time) is the class of problems solvable by an
interactive proof system
In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a ''prover'' and a ''verifier''. The parties interact by exchanging messages in order t ...
. It is equal to the class
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.
Formal definition
If we denote by SPACE(''t''(''n'')), the set of all problems that can b ...
. The result was established in a series of papers: the first by Lund, Karloff, Fortnow, and Nisan showed that co-NP had multiple prover interactive proofs; and the second, by Shamir, employed their technique to establish that IP=PSPACE. The result is a famous example where the proof does not
relativize.
The concept of an interactive proof system was first introduced by
Shafi Goldwasser
en, Shafrira Goldwasser
, name = Shafi Goldwasser
, image = Shafi Goldwasser.JPG
, caption = Shafi Goldwasser in 2010
, birth_place = New York City, New York, U.S.
, birth_date =
, death_date ...
,
Silvio Micali
Silvio Micali (born October 13, 1954) is an Italian computer scientist, professor at the Massachusetts Institute of Technology and the founder of Algorand. Micali's research centers on cryptography and information security.
In 2012, he received ...
, and
Charles Rackoff
Charles Weill Rackoff is an American cryptologist. Born and raised in New York City, he attended MIT as both an undergraduate and graduate student, and earned a Ph.D. degree in Computer Science in 1974. He spent a year as a postdoctoral scholar ...
in 1985. An interactive proof system consists of two machines, a prover, ''P'', which presents a proof that a given
string ''n'' is a member of some
language
Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of met ...
, and a verifier, ''V'', that checks that the presented proof is correct. The prover is assumed to be infinite in computation and storage, while the verifier is a probabilistic polynomial-time machine with access to a random bit string whose length is polynomial on the size of ''n''. These two machines exchange a polynomial number, ''p''(''n''), of messages and once the interaction is completed, the verifier must decide whether or not ''n'' is in the language, with only a 1/3 chance of error. (So any language in
BPP
BPP may refer to:
Education
* BPP Holdings, a holding company based in the United Kingdom
* BPP Law School, a law school based in the United Kingdom and a constituent school of BPP University
* BPP University, a private university based in the ...
is in IP, since then the verifier could simply ignore the prover and make the decision on its own.)
Definition
A language ''L'' belongs to IP if there exist ''V'', ''P'' such that for all ''Q'', ''w'':
:
:
The
Arthur–Merlin protocol
In computational complexity theory, an Arthur–Merlin protocol, introduced by , is an interactive proof system in which the verifier's coin tosses are constrained to be public (i.e. known to the prover too). proved that all (formal) languag ...
, introduced by
László Babai
László "Laci" Babai (born July 20, 1950, in Budapest) a fellow of the American Academy of Arts and Sciences, and won the Knuth Prize.
Babai was an invited speaker at the International Congresses of Mathematicians in Kyoto (1990), Zürich (1994, ...
, is similar in nature, except that the number of rounds of interaction is bounded by a constant rather than a polynomial.
Goldwasser et al. have shown that ''public-coin'' protocols, where the random numbers used by the verifier are provided to the prover along with the challenges, are no less powerful than private-coin protocols. At most two additional rounds of interaction are required to replicate the effect of a private-coin protocol. The opposite inclusion is straightforward, because the verifier can always send to the prover the results of their private coin tosses, which proves that the two types of protocols are equivalent.
In the following section we prove that IP = PSPACE, an important theorem in computational complexity, which demonstrates that an interactive proof system can be used to decide whether a string is a member of a language in polynomial time, even though the traditional
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.
Formal definition
If we denote by SPACE(''t''(''n'')), the set of all problems that can b ...
proof may be exponentially long.
Proof of IP = PSPACE
The proof can be divided in two parts, we show that IP ⊆ PSPACE and PSPACE ⊆ IP.
IP ⊆ PSPACE
In order to demonstrate that IP ⊆ PSPACE, we present a simulation of an interactive proof system by a polynomial space machine. Now, we can define:
:
and for every 0 ≤ ''j'' ≤ ''p'' and every message history ''M
j'', we inductively define the function ''N
Mj'':
:
where:
:
where Pr
''r'' is the probability taken over the random string ''r'' of length ''p''. This expression is the average of ''N
Mj+1'', weighted by the probability that the verifier sent message ''m
j+1''.
Take ''M''
0 to be the empty message sequence, here we will show that ''N
M0'' can be computed in polynomial space, and that ''N
M0'' = Pr
'V'' accepts ''w'' First, to compute ''N
M0'', an algorithm can recursively calculate the values ''N
Mj'' for every ''j'' and ''M
j''. Since the depth of the recursion is ''p'', only polynomial space is necessary. The second requirement is that we need ''N
M0'' = Pr
'V'' accepts ''w'' the value needed to determine whether ''w'' is in A. We use induction to prove this as follows.
We must show that for every 0 ≤ ''j'' ≤ ''p'' and every ''M
j'', ''N
Mj'' = Pr
j''">'V'' accepts ''w'' starting at ''Mj'' and we will do this using induction on ''j''. The base case is to prove for ''j'' = ''p''. Then we will use induction to go from ''p'' down to 0.
The base case of ''j'' = ''p'' is fairly simple. Since ''m
p'' is either accept or reject, if ''m
p'' is accept, ''N
Mp'' is defined to be 1 and Pr
j''">'V'' accepts ''w'' starting at ''Mj''= 1 since the message stream indicates acceptance, thus the claim is true. If ''m
p'' is reject, the argument is very similar.
For the inductive hypothesis, we assume that for some ''j''+1 ≤ ''p'' and any message sequence ''M
j+1'', ''N
Mj+1'' = Pr
j+1''">'V'' accepts ''w'' starting at ''Mj+1''and then prove the hypothesis for ''j'' and any message sequence ''M
j''.
If ''j'' is even, ''m
j+1'' is a message from ''V'' to ''P''. By the definition of ''N
Mj'',
:
Then, by the inductive hypothesis, we can say this is equal to
:
Finally, by definition, we can see that this is equal to Pr
j''">'V'' accepts ''w'' starting at ''Mj''
If ''j'' is odd, ''m
j+1'' is a message from ''P'' to ''V''. By definition,
:
Then, by the inductive hypothesis, this equals
:
This is equal to Pr
j''">'V'' accepts ''w'' starting at ''Mj''since:
: