IP (complexity)
Encyclopedia
In computational complexity theory
, the class IP (which stands for Interactive Polynomial time) is the class of problems solvable by an interactive proof system
. The concept of an interactive proof system was first introduced by Shafi Goldwasser
, Silvio Micali
, and Charles Rackoff
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
, 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
. These two machines exchange a polynomial number, 
, of messages and once the interaction is completed, the verifier must decide whether or not 
is in the language, with only a 1/3 chance of error. (So any language in BPP is in IP, since then the verifier could simply ignore the prover and make the decision on its own.)
More formally:
For any language L,
if 
:
The Arthur–Merlin protocol, introduced by Laszlo Babai
, 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
, 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
proof may be exponentially long.
are equal, we show that IP is a subset of PSPACE and also that PSPACE is a subset of IP, and hence the two are equivalent. In order to demonstrate that
, we present a simulation of an interactive proof system by a polynomial space machine.
Now, we can define:
and for every
and every message history 
, we inductively define the function 
:
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, the class IP (which stands for Interactive Polynomial time) is the class of problems solvable by an interactive proof system
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. The parties, the verifier and the prover, interact by exchanging messages in order to ascertain whether a given string belongs to a...
. The concept of an interactive proof system was first introduced by Shafi Goldwasser
Shafi Goldwasser
Shafrira Goldwasser is the RSA Professor of electrical engineering and computer science at MIT, and a professor of mathematical sciences at the Weizmann Institute of Science, Israel.-Biography:...
, Silvio Micali
Silvio Micali
Silvio Micali is an Italian-born computer scientist at MIT Computer Science and Artificial Intelligence Laboratory and a professor of computer science in MIT's Department of Electrical Engineering and Computer Science since 1983. His research centers on the theory of cryptography and information...
, and Charles Rackoff
Charles Rackoff
Charles Weill Rackoff is an American cryptologist. Born and raised in New York City, Rackoff 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 at INRIA in France.He currently works at the...
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
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
, 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
. These two machines exchange a polynomial number, , of messages and once the interaction is completed, the verifier must decide whether or not is in the language, with only a 1/3 chance of error. (So any language in BPP is in IP, since then the verifier could simply ignore the prover and make the decision on its own.)More formally:
For any language L,
if :
The Arthur–Merlin protocol, introduced by Laszlo Babai
László Babai
László Babai is a Hungarian professor of mathematics and computer science at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields...
, 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
, 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 PSPACEPSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
proof may be exponentially long.
Proof that IP = PSPACE
In order to prove that IP and PSPACEPSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
are equal, we show that IP is a subset of PSPACE and also that PSPACE is a subset of IP, and hence the two are equivalent. In order to demonstrate that
, we present a simulation of an interactive proof system by a polynomial space machine.Now, we can define:
and for every
and every message history , we inductively define the function :-
where the term
is defined as follows:
where
is the probability taken over the random string 
of length 
. This expression is the average of 
, weighted by the probability that the verifier sent message 
.
Take
to be the empty message sequence, here we will show that 
can be computed in polynomial space, and that 
. First, to compute 
, an algorithm can recursively calculate the values 
for every j and 
.
Since the depth of the recursion is p, only polynomial space is necessary. The second requirement is that we need
, the value needed to determine whether w is in A. We use induction to prove this as follows.
We must show that for every
and every 
, 
, and we will do this using induction on j. The base case is to prove for 
. Then we will use induction to go from p down to 0.
The base case
is fairly simple. Since 
is either accept or reject, if 
is accept, 
is defined to be 1 and \Pr[V accepts w starting at 
] = 1 since the message stream indicates acceptance, thus the claim is true. If 
is reject, the argument is very similar.
For the inductive hypothesis, we assume that for some
and any message sequence 
, 
and then prove the hypothesis for 
and any message sequence 
.
If j is even,
is a message from V to P. By the definition of 
, 
. Then, by the inductive hypothesis, we can say this is equal to 
. Finally, by definition, we can see that this is equal to 
.
If j is odd,
is a message from P to V. By definition, 
. Then, by the inductive hypothesis, this equals 
. This is equal to 
since:
because the prover on the right-hand side could send the message
to maximize the expression on the left-hand side. And:
Since the same Prover cannot do any better than send that same message. Thus, this holds whether
is even or odd and the proof that IP 
PSPACE is complete.
Here we have constructed a polynomial space machine that uses the best prover
for a particular string 
in language 
. We use this best prover in place of a prover with random input bits because we are able to try every set of random input bits in polynomial space. Since we have simulated an interactive proof system with a polynomial space machine, we have shown that IP 
PSPACE, as desired.
PSPACE is a subset of IP
In order to illustrate the technique that will be used to prove
, we will first prove a weaker theorem, which was proven by Lund, et al.: 
. Then using the concepts
from this proof we will extend it to show that
. Since TQBF 
PSPACE-Complete, and 
then PSPACE 
IP.
#SAT is a member of IP
We begin by showing that
, where:
-
is a cnf-formula with exactly 
satisfying assignments 
.
Note that this is different from the normal definition of #SATSharp-PIn computational complexity theory, the complexity class #P is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute ƒ," where ƒ is the number of accepting paths of a nondeterministic...
, in that it is a decision problem, rather than a function.
First we use arithmetization to map the boolean formula with
variables, 
to a polynomial 
, where 
mimics 
in that 
is 1 if 
is true and 0 otherwise provided that the variables of 
are assigned Boolean values. The Boolean operations 
, 
, and 
used in 
are simulated in 
by replacing the operators in 
as shown in the table below.
Arithmetization rules for converting a Boolean formula 
to a polynomial 
As an example,
would be converted into a polynomial as follows:
The operations
and 
each result in a polynomial with a degree bounded by the sum of the degrees of the polynomials for 
and 
and hence, the degree of any variable is at most the length of 
.
Now let
be a finite field with order 
; also demand that q be at least 1000. For each 
, define a function 
on F, having parameters 
, and a single variable 
: For 
and for 
let 
. Note that the value of 
is the number of satisfying assignments of 
. 
is a void function, with no variables.
Now the protocol for
works as follows:
- Phase 0:
The prover
choses a prime 
and computes 
, it then sends 
and 
to the verifier 
. 
checks that 
is a prime greater than 
and that 
. - Phase 1:
sends the coefficients of 
as a polynomial in z. 
verifies that the degree of 
is less than 
and that 
. (If not 
rejects). 
now sends a random number 
from 
to 
. - Phase i:
sends the coefficients of 
as a polynomial in 
. 
verifies that the degree of 
is less than 
and that 
. (If not 
rejects). 
now sends a random number 
from 
to 
. - Phase n+1:
evaluates 
to compare to the value 
. If they are equal 
accepts, otherwise 
rejects.
Note that this is a public-coin algorithm.
If
has 
satisfying assignments, clearly 
will accept. If 
does not have 
satisfying assignments we assume there is a prover 
that tries to convince 
that 
does have 
satisfying assignments. We show that this can only be done with low probability.
To prevent
from rejecting in phase 0, 
has to send an incorrect value 
to 
. Then, in phase 1, 
must send an incorrect polynomial 
with the property that 
. When 
chooses a random 
to send to 
, 
. This is because a polynomial in a single variable of degree at most 
can have no more than 
roots (unless it always evaluates to 0). So, any two polynomials in a single variable of degree at most 
can be equal only in 
places. Since 
the chances of 
being one of these values is at most 
if n > 10, or at most 
if 
.
Generalizing this idea for the other phases we have for each
if 
, then for 
chosen randomly from 
, 
. There are 
phases, so the probability that 
is lucky because 
selects at some stage a convenient 
is at most 
. So, no prover can make the verifier accept with probability greater than 
. We can also see from the definition that the verifier 
operates in probabilistic polynomial time. Thus, 
.
TQBF is a member of IP
In order to show that PSPACE is a subset of IP, we need to choose a PSPACE-Complete problem and show that it is in IP. Once we show this, then it clear that PSPACE
IP. The proof technique demonstrated here is credited to Adi ShamirAdi ShamirAdi Shamir is an Israeli cryptographer. He is a co-inventor of the RSA algorithm , a co-inventor of the Feige–Fiat–Shamir identification scheme , one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer...
We know that TQBF is in PSPACE-Complete. So let
be a quantified boolean expression:
where
is a CNF formula. Then 
is a quantified, either 
or 
. Now 
is the same as in the previous proof, but now it also includes quantifiers.
-
Here,
is 
with 
to 
substituted for 
to 
. Thus 
is the truth value of 
. In order to arithmetize 
we must use the following rules:
where as before we define x * y = 1 − (1 − x)(1 − y).
By using the method described in
, we must face a problem that for any 
the degree of the resulting polynomial may double with each quantifier. In order to prevent this, we must introduce a new reduction operator R which will reduce the degrees of the polynomial without changing their behavior on Boolean inputs.
So now before we arithmetize
we introduce a new expression:
r way:
Now for every i
k we define the function 
. We also define 
to be the polynomial 
which is obtained by arithmetizing 
. Now in order to keep the degree of the polynomial low, we define 
in terms of 
:
Now we can see that the reduction operation R, doesn't change the degree of the polynomial. Also it is important to see that the
operation doesn't change the value of the function on boolean inputs. So 
is still the truth value of 
, but the 
value produces a result that is linear in x. Also after any 
we add 
in 
in order to reduce the degree down to 1 after arithmetizing 
.
Now let's describe the protocol. If
is the length of 
, all arithmetic operations in the protocol are over a field of size at least n4 where n is the length of 
.
- Phase 0:
: P sends 
to V. V checks that 
and rejects if not.
- Phase 1:
: P sends 
to V. V uses coefficients to evaluate 
and 
. Then it checks that the polynomial's degree is at most 
and that the following identities are true:
If either fails then reject.
- Phase i:
: P sends 
as a polynomial in 
. 
denotes the previously set random values for 
V uses coefficients to evaluate
and 
. Then it checks that the polynomial degree is at most 
and that the following identities are true:
-
-
-
If either fails then reject.
: V picks a random 
in 
and sends it to P. (If S=R then this 
replaces the previous 
).
Goto phase i + 1 where P must persuade V that
is correct.
- Phase k + 1:
V evaluates
. Then it checks if 
If they are equal then V accepts, otherwise V rejects.
This is the end of the protocol description.
If
is true then V will accept when P follows the protocol. Likewise if 
is a malicious prover which lies, and if 
is false, then 
will need to lie at phase 0 and send some value for 
. If at phase i, V has an incorrect value for
then 
and 
will likely also be incorrect, and so forth. The probability for 
to get lucky on some random 
is at most the degree of the polynomial divided by the field size: 
. The protocol runs through 
phases, so the probability that 
gets lucky at some
phase is
. If 
is never lucky, then V will reject at phase k+1.
Since we have now shown that both IP
PSPACE and PSPACE 
IP, we can conclude that IP = PSPACE as desired. Moreover, we have shown that any IP algorithm may be taken to be public-coin, since the reduction from PSPACE to IP has this property.
Variants
There are a number of variants of IP which slightly modify the definition of the interactive proof system. We summarize some of the better-known ones here.
MIP
In 1988, Goldwasser et al. created an even more powerful interactive proof system based on IP called MIP in which there are two independent provers. The two provers cannot communicate once the verifier has begun sending messages to them. Just as it's easier to tell if a criminal is lying if he and his partner are interrogated in separate rooms, it's considerably easier to detect a malicious prover trying to trick the verifier if there is another prover it can double-check with. In fact, this is so helpful that Babai, Fortnow, and Lund were able to show that MIP = NEXPTIME, the class of all problems solvable by a nondeterministic machine in exponential time, a very large class. Moreover, all languages in NP have zero-knowledge proofs in an MIP system, without any additional assumptions; this is only known for IP assuming the existence of one-way functions.
IPP
IPP (unbounded IP) is a variant of IP where we replace the BPP verifier by a PPPP (complexity)In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time...
verifier. More precisely, we modify the completeness and soundness conditions as follows:
- Completeness: if a string is in the language, the honest verifier will be convinced of this fact by an honest prover with probability at least 1/2.
- Soundness: if the string is not in the language, no prover can convince the honest verifier that it is in the language, except with probability less than 1/2.
Although IPP also equals PSPACE, IPP protocols behaves quite differently from IP with respect to oraclesOracle machineIn complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
: IPP=PSPACE with respect to all oracles, while IP ≠ PSPACE with respect to almost all oracles.
QIP
QIPQuantum Interactive ProtocolIn computational complexity theory, the class QIP, which stands for Quantum Interactive Polynomial time, is the quantum computing analogue of the classical complexity class IP, which is the set of problems solvable by an interactive proof system with a polynomial-time verifier and one...
is a version of IP replacing the BPP verifier by a BQPBQPIn computational complexity theory BQP is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances...
verifier, where BQP is the class of problems solvable by quantum computerQuantum computerA quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...
s in polynomial time. The messages are composed of qubits. In 2009, Jain, Ji, Upadhyay, and Watrous proved that QIP also equals PSPACE, implying that this change gives no additional power to the protocol. This subsumes a previous result of Kitaev and Watrous that QIP is contained in EXPTIMEEXPTIMEIn computational complexity theory, the complexity class EXPTIME is the set of all decision problems solvable by a deterministic Turing machine in O time, where p is a polynomial function of n....
because QIP = QIP[3], so that more than three rounds are never necessary.
compIP
Whereas IPP and QIP give more power to the verifier, a compIP system (competitive IP proof system) weakens the completeness condition in a way that weakens the prover:
- Completeness: if a string is in the language L, the honest verifier will be convinced of this fact by an honest prover with probability at least 2/3. Moreover, the prover will do so in probabilistic polynomial time given access to an oracle for the language L.
Essentially, this makes the prover a BPP machine with access to an oracle for the language, but only in the completeness case, not the soundness case. The concept is that if a language is in compIP, then interactively proving it is in some sense as easy as deciding it. With the oracle, the prover can easily solve the problem, but its limited power makes it much more difficult to convince the verifier of anything. In fact, compIP isn't even known or believed to contain NPNP (complexity)In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
.
On the other hand, such a system can solve some problems believed to be hard. Somewhat paradoxically, though such a system is not believed to be able to solve all of NP, it can easily solve all NP-completeNP-completeIn computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problems due to self-reducibility. This stems from the fact that if the language L is not NP-hard, the prover is substantially limited in power (as it can no longer decide all NP problems with its oracle).
Additionally, our earlier proof that graph nonisomorphism is in IP also shows that it is in compIP, since the only hard operation the prover ever does is isomorphism testing, which it can use the oracle to solve. Quadratic non-residuosity and graph isomorphism are also in compIP. (Note, Quadratic non-residuosity (QNR) is likely an easier problem than graph isomorphism as QNR is in UP intersect coUP.
-
-
-
-
-
