Aachen University of Technology (RWTH) Teaching and Research Area Theoretical Computer Science

Prof. Peter Rossmanith

Seminar on Result Checking at Runtime

(Ergebnisprüfung zur Laufzeit) 2003/2004

The impact of interactivity and randomness on complexity theory

Eric Bodden

November 2003

seminar@bodden.de

This document may be found at: http://www.bodden.de

Abstract

During the last three decades the introduction of randomization and interactivity into proof systems has been widely discussed in the scene of complexity. Pioneers in this area were Babai [Bab85] and Goldwasser et al.[GMR85] who both introduced firstly independent extensions of the formerly known single-way NP proof system to a more powerful system making use of both, interaction and randomization.

The introduction of the two new features into proof systems yielded several new complexity classes just beyond NP, so leading to finer granularity in deciding the complexity of certain algorithms. Also the newly introduced notion of interactive proofs and randomized proof systems provided new ways of finding reductions of known problems. Applications of such reductions were, e.g., an efficient interactive checker for the permanent of a matrix as well as for graph non-isomorphism.

This paper introduces the systems suggested by Babei, Goldwasser et al.elaborates on the newly defined complexity classes from these systems as well as on some applications. This script also is a preparation for the two important equality proofs of IP and PSPACE as well as NP and PCP which are also described in this series.

1 A short review on complexity

Before defining the complexity classes based on interaction and randomization, we firstly give a short review of the basic classes P and NP and provide an alternative, descriptive definition for them. This latter definition is important to gain an intuitive understanding of the relation between these classes and the ones we are going to derive in this paper.

1.1 The class P

P is known as the class of all algorithms that can be computed in polynomial time:

P = ⋃_{k∈ℕ} T IME(n^{k})  (1)

In the notion of Turing Machines, that means that for the given problem of size n there exists a deterministic Turing Machine M that computes a solution to this problem in not more than n^{k} steps for some natural Number k. Speaking in proofs, one would say that a proof can be computed in polynomial time.

1.2 The class NP

The usual definition of the class NP, however, differs in first instance since it introduces non-determinism through the use of NT IME, which refers to all nondeterministic Turing machines with the given time complexity:

NP = ⋃_{k∈ℕ} NT IME(n^{k})  (2)

A rather descriptive approach, however, is the following: A problem is in NP if a proof of membership can be verified in polynomial time. This definition leads to the concepts of verifiers. If a polynomial verifier exists for a given problem, then the problem is in NP.

1.2.1 Example: 3SAT

3SAT is a very famous problem because it was the very first problem to be proven to be NP-complete [Coo71].

• Input: A boolean formula φ in 3-KNF:

φ = ⋀ _{i=1}^{m} (w_{i_{1}},w_{i_{2}},w_{i_{3}})

• Output: Yes, if φ is satisfiable, No, if otherwise.

From this problem we can derive a language L as follows:

L = {x ∈ {0,1}^{3m}|φ(x) = 1}  (3)

which is the language of all possible solutions to φ. This approach of constructing a language to express the result of a problem is general to all complexity estimations. Given such a language it is possible to interpret the computation of a solution to a given problem as computation of a proof of membership to this solution language for any input x.

For this specific problem Cook proved that it is NP complete. Especially, as long as P ≠ NP, there exists no algorithm that could compute such a proof of membership in polynomial time. However, as one can easily see, given a specific solution instance x′, in 3SAT it is easy to verify if x′ really is a solution to this problem, just by substituting the variables in 3 with the given input and calculating the result. This particularly can be done in polynomial time. The observation is that, as mentioned above, the set of languages in NP can be seen as the set of languages that allow efficient verification of membership proofs.

For languages in NP, such proofs can always be fully encoded in such a way that they can be fully passed to a verifier, combined with the given input, so that this verifier can instantly check if the supposed solution is an actual one. However, one might argue that there certainly are problems, where this property of full encoding does not hold - e.g. languages, where request by the verifier might be necessary. Or, on the other hand, languages that might be verified efficiently but only by the means of randomization and thus by accepting a slight error probability.

2 Probability and interactive proofs

In this paper we describe two different enhancements of this concepts and their combination. The first enhancement is the use of interaction, which is introduced using so-called Arthur/Merlin games [Bab95]. Babai introduced this system in 1985 and utilized two characters, King Arthur and the all-powerful Merlin for the description of an interactive proof system, Merlin being the prover and Arthur the verifier for the supposed proof that Merlin provides. Goldwasser et al.describe a similar system with a slightly different communication protocol. Such verifiers, however, give the right answer only with a certain probability because they employ nondeterministic coin tosses, as we will see.

This leads us to the second enhancement which is the release of the constraint that the verification needs to be perfectly correct. If one considers instead a system of verifiers that allow ”false positives” with a certain small probability, one gains a new complexity hierarchy of probability-based complexity classes for noninteractive proofs.

2.1 Arthur/Merlin games

An interactive proof is a game between two players. On the one hand one has the all-powerful sorcerer Merlin, who in the complexity sense is an unconstrained prover. His goal is to convince Arthur of the membership/non-membership of a given input x to a given problem language (as mentioned on page 3). On the other hand we have King Arthur, who tries to verify whether what Arthur suggests is true. Since Arthur is just human, he has only polynomial time for each computation.

2.1.1 Protocol

The actions defining the game are described by the following protocol.

• Both players communicate by writing polynomial length strings on two communication tapes, one only writable, the other only readable for each.

• Merlin’s state depends on two elements: The input string x and the strings he previously wrote to the tape already. His strategy is defined as a deterministic function on this data.

• Arthur moves in polynomial time depending also on the input x, again the string previously printed to the tape but now also depending on a coin toss, formally being the input of an infinite random tape that he occupies.

• The game ends after a finite number of steps, in the end having Arthur entering one of the two possible states Merlin wins (proof is correct with a certain probability) or Arthur wins (Merlin was proven wrong).

From the above definition it is obvious that the nondeterministic choice in Arthur’s function introduces non-determinism. This again induces a certain uncertainty for the result. In the worst case this could lead to a situation where the probability of the proof system accepting certain inputs x_{i}, is exactly 1/2. This would of course not be a valuable statement at all. For that reason, it is postulated that the probabilities are bounded away from 1/2. This yields the following definition of a valid Arthur/Merlin protocol as follows:

Definition 1 (Valid Arthur/Merlin protocol). A valid Arthur/Merlin protocol (M,A) for a language L is a system of two interactive Touring Machines (as defined in [Bab85]) A and M, which satisfies the following constraints:

1. (Efficiency) (M,A) is polynomially bounded and A is polynomial-time computable.

2. (Completeness) If x ∈ L, then A accepts x with probability of at least 2/3 in (M,A)(x).

3. (Soundness) If x ∉ L, then for any M′, A accepts x with probability of at most 1/3 in (M′,A)(x).

In this definition, the completeness condition seemingly postulates that for any true solution such an instance can be relatively easily identified. The soundness condition respectively assures that it is hard enough to cheat on the verifier using any proving strategy whatsoever.

As we saw in section 1.1, the existence of a nondeterministic, polynomial-time verifier defined the complexity class NP. So it is just natural to ask if definition 1 of an A/M proof system also yields a complexity class and if so if this is probably even somehow related to the notion of NP we had beforehand already. The complexity classes that derive from A/M protocols are as follows:

Definition 2 (AM(t(n))). For a given language L and any polynomial function t(n) it is said that L ∈ AM(t(n)) if there exists a valid Arthur/Merlin protocol (M,A) for L with at most t(n) steps of interaction on any given input x ∈ L. Convention: For any constant c ∈ ℕ, AM(c) is defined accordingly.

Please note that in literature one may also find class labels following the system M = MA(1),A = AM(1),AMA = AM(3) etc. depending on whether Arthur or Merlin moves first.

2.1.2 The hierarchy collapses

One very surprising result about AM was shown in 1985 [Bab85]: For any n > 1, it holds that AM(k) = AM(2). So, in other words, any protocol utilizing more than one step of interaction can be reduced to an equivalent protocol where only exactly two steps are necessary: Arthur communicates his coin toss(es) and Merlin his proof respectively. Mentioning this reduction one should on the other hand also note, that it is still to be shown if it can be performed without increasing the complexity of the prover. The reductions currently known do certainly increase its complexity and it is not known if one can do any better. However since by definition the prover is unconstrained in complexity, such reductions are still valid.

So since for all constants n ∈ N the classes AM(n) were reduced to exactly two, namely AM(1) and AM(2) (AM for short), one might notice that the one special class AM(1) is actually the class BPP (Bounded error probability in polynomial time), because it does not involve any interaction at all. Respectively, looking at MA(1), the only difference to NP is that MA(1) involves randomization. But considering that there actually exist sufficient pseudo random generators nowadays, the verification can be simulated in deterministic polynomial time. So one can conclude that under believable complexity assumptions MA(1)=NP.

To conclude this chapter now, we summarize that the notion of Arthur/Merlin games defines a new set of complexity classes just above NP. NP can be identified as a special case of the protocol. However, the protocol does allow definition of more powerful classes which leads to a finer granularity in determining problem complexities beyond NP. The final inclusion hierarchy we gain is:

NP = MA(1) ⊆ AM(2) ⊆ AM(t(n)) ⊆ AM(t(n + 1))  (4)

2.2 Interactive proofs

As mentioned above simultaneously to Babai, Goldwasser at al. defined a similar proof system under the notion of Interactive Proofs (IPs), initially for cryptographic applications. Arthur is here simply called the verifier V, Merlin the prover P accordingly. Both systems are almost equal. The only difference in the definition is that in A/M games, Arthur’s coin tosses are public, so that Merlin, the prover, knows about them. The proof is not a zero-knowledge proof. But Goldwasser et al. rather defined the random choices in an IP protocol to be private, which actually seems to be an essential constraint for some proofs. As an example consider the following valid IP protocol ([BK89]) :

2.2.1 Example: Graph-Non-Isomorphism

Consider the following problem:

• Input: Two graphs G_{0} = (V_{0},E_{0}) and G_{1} = (V_{1},E_{1}).

• Output: YES if G_{0} is not isomorphic to G_{1}, NO otherwise.

The protocol works as follows:

1. V: Uniformly select b ∈ {0,1}. Uniformly select a permutation π on V_{b}. So let H = π(G_{b}). Send H to P.

2. P: If G_{0} ≅ H return r = 0, else return r = 1 to V. (*)

3. V: Accept, if r = b, else reject.

Please note that by repeating step (*) k times, one can so assure that the probability of P cheating is less or equal than 1/2^{k}. That does not necessarily also require involve k or even 2k steps of communication: V could send all k coin tosses at once and so could P send an answer to all these queries in one string, which would still be polynomial bounded.

Based on the notion of an interactive proof system one can define the classes IP accordingly:

Definition 3. Valid Interactive Proof protocol A valid IP protocol (P,V) for a language L is a system of two interactive Touring Machines (see [GMR85]) P and V, which satisfies the following constraints:

1. (Efficiency) (P,V) is polynomially bounded and V is polynomial-time computable.

2. (Completeness) If x ∈ L, then V accepts x with probability of at least 2/3 in (P,V)(x).

3. (Soundness) If x ∉ L, then for any P′, V accepts x with probability of at most 1/3 in (P′,V)(x).

Please not that in unlike the definition of AM=AM(2), IP is defined as:

IP = IP(poly) = ⋃_{k≥1} IP(n^{k}),n ∈ ℕ  (5)

So, as one can easily see, the above definition does not differ at all from the definition of an A/M proof system but in the definition of the interactive proof system (the Touring Machines) itself. While in an A/M proof system the verifier’s coin tosses are public, in an IP proof system they are not. And considering the example above, this privacy seems to be essential for certain IP proofs.

So it was very surprising that in 1989 Goldwasser and Sipser proved [GS89] that the following always holds true:

∀t(n),IP(t(n)) = AM(t(n))  (6)

Especially this result yields with (5) that

IP = ⋃_{k≥1} AM(n^{k}),n ∈ ℕ.  (7)

So since it was shown, that the definition of the IP protocol did not give a real gain of complexity classes Ben-Or et al.studied in 1988 if the introduction of multiple provers to an IP would yield any new results.

2.3 Multiple provers

A multi-prover interactive proof system is an interactive proof system with multiple provers where the provers have no means of communicating with each other but the verifier has a communication channel to each of those.

Definition 4 (MIP(m)). A language L is in MIP(m), m ≥ 2, if there exists a multiprover interactive protocol (P_{1},...,P_{m},V) that satisfies the constraints as in Definition 3 for every prover P_{1},...,P_{m}.

Surprisingly, Ben-or et al.showed in [BGKW88] that exactly two provers always suffice. This yields the definition

MIP = MIP(n) ∀n ≥ 2.  (8)

2.3.1 Applications

Initially it was assumed that MIP was only a slight extension of IP and even NP, also that coNP ⊈ MIP. So it was quite a surprise^{1} when Shamir proved 1992 that IP = PSPACE [SPotA92], because PSPACE is believed to be far more powerful than NP and coNP.

1The surprise was even bigger considering that in [CCL91] it was shown that IP ≠ PSCAPE with probability 1 (with respect to a random oracle).

In 1991 then Babai, Fortnow and Lund also showed that MIP = NEXP [BFL91]. This result seems really impressive since in other words it means that for every language that admits exponentially long proofs, these proofs can be encoded to serve as input for a polynomial time multi-prover interactive verifier.

After this was proven, people were wondering if it was possible to scale this result down to another representation of NP. Since membership proofs for NP have polynomial length, one might guess that verification of such proofs could be done in polylogarithmic time. But this is unfortunately not feasible since the verifier at least needs to read the input, which is truly linear. Nevertheless Babai, Fortnow, Levin and Szegedy showed in 1991 [BFLS91] that the input to the verifier can, using special error-correcting codes, be encoded in such a way that it can be read and checked in polylogarithmic time.

Another scaling-down approach, this time in the sense of space, was performed 1996 by Feige et al.. [FGL^{+} 96]. They showed that without loss of generality it suffices for polynomial time NP verifiers to only use O(log(n) log(log(n))) random bits and query bits.

For further explorations of this and other results we refer the diligent reader to [Tre00] and [AS98].

As we saw through the introduction of multiple provers, another complexity class was introduced, which showed the actual power of interaction. Problems that formerly took exponential verification time can now be verified by a poly-time interactive system.

2.4 Probabilistically Checkable Proofs

Inspired by these results and by new, more efficient reductions of the clique problem, Arora and Safra introduced [AS98] in 1998 the class of Probabilistically Checkable Proofs (PCPs). These proofs do not utilize any interaction, but are also very scalable in another sense: In the sense of necessary query and random bits as well as the probability of accepting / rejecting an input word. The combination of these four parameters yields a very flexible system that is able to describe many previously classes in sometimes several different ways. Some results also bear a so far unknown proximity of the classes P and NP. Arora and Safra are able to prove several implications that, if one of the premises can ever be satisfied, it follows immediately that P=NP. Arora and Safra define the verifiers used to define PCPs as follows.

Definition 5 (PCP verifier). Let L be a language, π be a membership proof, τ a random string and M a verifier for which M^{π}(x,τ) : L×{0,1}^{ω} → {accept,reject}. A verifier M checks membership proofs for L if for every input x

1. If x ∈ L then ∃ π so that

P_{π}[M^{π}(x,τ) = 1] = 1.

2. If x ∉ L then ∀ π so that

P_{π}[M^{π}(x,τ) = 1] < \frac{1}{2}.

Such a verifier in allowed random access to the proof π. The action of such an access will be called a query. Now for any integer valued function r, q Arora et al.say that M is (r(n),q(n))-restricted, if for any input x with |x| = n M uses at most r(n) random bits for its computation and queries at most q(n) bits from the the proof string. The verification protocol is defined as follows:

• Read the input X and the random string τ.

• Compute in poly(n) time the query locations i_{1}(x,τ),..,i_{O(q(n))}(x,τ).

• Load the appropriate bits π[i_{1}(x,τ)],..,π[i_{O(q(n))}(x,τ)] of the proof to the work tape.

• Proceed with a poly(n) time computation on the work tape to decide whether to enter the accept or reject state.

Now one can gain immediately the following definition of the PCP classes:

Definition 6 (PCP). ^{2} A language L is in PCP[r(n),q(n)] if there exists an (r(n),q(n))- restricted Verifier that checks membership proofs for L.

With this definition now one can easily identify the class NP as PCP(0,poly(n)), because NP proofs do not make use of randomization at all and are able to verify polynomial-size membership proofs.

3 Conclusion

As we saw, the introduction of two simple new features to the well-known NP proof system, namely randomization and interaction, yielded quite an unexpected power of these newly created systems. New, stable complexity classes were born, some of which could be identified as the known classes NP, PSPACE and NEXPTIME. This crosscutting property of the new and old view of the complexity world helped to find new reductions. These again lead to new, formerly unknown relations between complexity classes. Altogether the interactive proof protocols turned out to be powerful enough to go far beyond the ordinary reduction systems based on NP completeness.

2Sometimes the definition is extended to PCP_{a,b}[r(n),q(n)] for verifiers that have a probability distribution of a,b for the accepting and rejecting states. So PCP[r(n),q(n)] = PCP_{1,1/2}[r(n),q(n)]

4 Suggested reading

[Bab85] and [GMR85] are the first papers about interactive proofs at all. [Bab95] gives a good, intuitive interpretation of such systems and the results gained so far.

[Vad] as well ad [Tre00] give a good introduction to the whole topic of interactive proofs and features some results gained during the last years. The former also demonstrate some example protocols. [AS98] gives a good overview about results and how the systems are connected together, especially IP and PCP. [BK89] supposes a big variety of protocols for interactive proof systems. The proof for AM(t(n)) = IP(t(n)) can be found in [GS89] as well as [BDG90], chapter 11.

5 Acknowledgements

I wish to thank Stefan Richter, Peter Rossmanith and Joachim Kneis for quite some fruitful discussions. Also much gratitude goes to André Hildebrandt and his colleagues for the professional proofreading of this paper.

References

[AS98] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: a new characterization of np. J. ACM, 45(1):70–122, 1998.

[Bab85] L Babai. Trading group theory for randomness. In 17th annual ACM symposium on Theory of computing, pages 421–429. ACM Press, 1985.

[Bab95] L Babai. E-mail and the unexpected power of interaction. In 5th IEEE Structure in Complexity Theory Conference, pages 30–44. IEEE, 1995.

[BDG90] J. Balcazar, J. Daz, and J. Gabarro. Structural Complexity II. Springer-Verlag, Berlin, 1990.

[BFL91] L Babai, Lance Fortnow, and Carsten Lund. Non-deterministic exponential time has two-prover interactive protocols. In IEEE Symposium on Foundations of Computer Science, pages 16–25, 1991.

[BFLS91] László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 21–32. ACM Press, 1991.

[BGKW88] Michael Ben-Or, Shafi Goldwasser, Joe Kilian, and Avi Widgerson. Multi-prover interactive proofs: how to remove intractability. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 113–131. ACM Press, 1988.

[BK89] M. Blum and S. Kanna. Designing programs that check their work, 1989.

[CCL91] J. Cai, A. Condon, and R. J. Lipton. PSPACE is provable by two provers in one round. In Structure in Complexity Theory Conference, pages 110–115, 1991.

[Coo71] Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing, pages 151–158. ACM Press, 1971.

[FGL^{+} 96] Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. J. ACM, 43(2):268–292, 1996.

[GMR85] S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof-systems. In Proceedings of the seventeenth annual ACM symposium on Theory of computing, pages 291–304. ACM Press, 1985.

[GS89] S. Goldwasser and M. Sipser. Private coins versus public coins in interactive proof systems. Advances in Computing Research, 5:73– 90, 1989.

[SPotA92] A. Shamir, I. PSPACE, o the, and A. Preliminary version, 1992.

[Tre00] Trevisan. Interactive and probabilistic proof-checking. ANNALSPAL: Annals of Pure and Applied Logic, 104, 2000.

[Vad] Salil Vadhan. Probabilistic proof systems - part i.