×

zbMATH — the first resource for mathematics

Non-deterministic exponential time has two-prover interactive protocols. (English) Zbl 0774.68041
Summary: We determine the exact power of two-prover interactive proof systems introduced by M. Ben-Or, S. Goldwasser, J. Killian and A. Wigderson [Multi-prover interactive proofs: How to remove the intractability assumptions, in Proc. 20th Ann. ACM Symp. Theory of Computing, 113-131 (1988)]. In this system, two all-powerful noncommunicating provers convince a randomizing polynomial time verifier in polynomial time that the input \(x\) belongs to the language \(L\). We show that the class of languages having two-prover interactive proof systems in nondeterministic exponential time.
We also show that to prove membership in languages in \(EXP\), the honest provers need the power of \(EXP\) only.
The first part of the proof of the main result extends recent techniques of polynomial extrapolation used in the single prover case by C. Lund, L. Fortnow, H.Karloff and N.Nisan [Algebraic methods for interactive proof systems, in Proc. 31st Ann. IEEE Symp. Foundations of Comp. Sci., 1-10 (1990)] and A. Sharmir [IP=PSPACE, in Proc. 31st Ann. IEEE Symp. Foundations of Comp. Sci., 11-15 (1990)]. The second part is a verification scheme for multilinearity of the function in several variables held by an oracle and can be viewed as an independent result on program verification. Its proof rests on combinatorical techniques employing a simple isoperimetric inequality for certain graphs.

MSC:
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q60 Specification and verification (program logics, model checking, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A. V. Aho, J. E. Hopcroft, andJ. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading MA, 1974. · Zbl 0326.68005
[2] D. Aldous, On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing.Probability in the Engineering and Informational Sciences 1 (1987), 33-46. · Zbl 1133.60327
[3] L. Babai, Trading group theory for randomness, inProc. 17th Ann. ACM Symp. Theory of Computing, 1985, 421-429.
[4] L. Babai, E-mail and the unexpected power of interaction, in: Proc. 5th Ann. IEEE Structures in Complexity Theory Conf., 1990, 30-44.
[5] L. Babai andP. Erd?s, Representation of group elements as short products,Annals of Discrete Mathematics 12 (1982), 27-30.
[6] L. Babai andL. Fortnow, Arithmetization: a new method in structural complexity theory,Computational Complexity 1 (1991), 41-66. (Preliminary version appeared as: A characterization of #P by arithmetic straight line programs, inProc. 31st Ann. IEEE Symp. Foundations of Comp. Sci., 1990, 26-34.) · Zbl 0774.68040
[7] L. Babai, L. Fortnow, L. Levin, and M. Szegedy, Checking computations in polylogarithmic time, in:Proc 23rd ACM Symp. Theory of Computing, 1991, to appear.
[8] L. Babai, L. Fortnow, and C. Lund, Non-deterministic exponential time has two-prover interactive protocols (extended abstract),Proc. 31st Ann. IEEE Symp. Found. Comp. Sci., 1990, 16-25. · Zbl 0774.68041
[9] L. Babai and P. Frankl,Linear Algebra Methods in Combinatorics, I, Preliminary Version, University of Chicago, Dept. C. S. 1988.
[10] D. Beaver and J. Feigenbaum, Hiding instances in multioracle queries, inProc. 7th Symp. on Theoretical Aspects of Comp. Sci. Lecture Notes in Comp. Sci. 415 (1990), 37-48. · Zbl 0733.68005
[11] M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson, Multiprover interactive proofs: How to remove the intractability assumptions, inProc. 20th Ann. ACM Symp. Theory of Computing, 1988, 113-131.
[12] M. Blum and S. Kannan, Designing programs that check their work, inProc. 21st Ann. ACM Symp. Theory of Computing, 1989, 86-97.
[13] M. Blum, M. Luby, and R. Rubinfeld, Self-testing and self-correcting programs, with applications to numerical programs, inProc. 22nd Ann. ACM Symp. Theory of Computing, 1990, 73-83.
[14] L. Babai andS. Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes.J. Comp. Sys. Sci. 36 (1988), 254-276. · Zbl 0652.03029
[15] J. Cai, PSPACE is provable by two provers in one round, manuscript, 1990.
[16] S. A. Cook, The complexity of theorem proving procedures, inProc. 3rd Ann. ACM Symp. Theory of Computing 1971, 151-158.
[17] U. Feige, S. Goldwasser, L. Lovász, and S. Safra, On the complexity of clique approximation, in preparation.
[18] P. Feldman, The Optimum Prover lives inPSPACE, manuscript, 1986.
[19] L. Fortnow, The Complexity of Perfect Zero-Knowledge, In S. Micali, ed.,Randomness and Computation, Advances in Computing Research 5 (1989), 327-343.
[20] L. Fortnow, Complexity-Theoretic Aspects of Interactive Proof Systems, Ph.D. Thesis,Massachusetts Institute of Technology, Laboratory for Computer Science, Tech. Report MIT/LCS/TR-447 1989.
[21] L. Fortnow, J. Rompel, and M. Sipser, On the power of multiprover interactive protocols,Proc. 3rd Structure in Complexity Theory Conf., 1988, 156-161. · Zbl 0938.68824
[22] L. Fortnow andM. Sipser, Are there interactive protocols for co-NP languages?,Inf. Process. Letters 28 (1988), 249-251. · Zbl 0668.68054
[23] S. Goldwasser, S. Micali, andC. Rackoff, The knowledge complexity of interactive proofs,SIAM J. Comput. 18 (1989), 186-208. (Preliminary version appeared inProc. 18th Ann. ACM Symp. Theory of Computing, 1985, 291-304.) · Zbl 0677.68062
[24] J. Hartmanis, N. Immerman, andV. Sewelson, Sparse sets inNP-P: EXPTIME versusNEXPTIME, Inf. and Control 65 (1985), 158-181. · Zbl 0586.68042
[25] H. Heller On Relativized Exponential and Probabilistic Complexity Classes,Information and Computation 71 (1986), 231-243. · Zbl 0628.68047
[26] R. Karp, R. Lipton, Some Connections between Nonuniform and Uniform Complexity Classes,Proc. 12th Ann. ACM Symp. Theory of Computing, 1980, 302-309.
[27] L. Levin, Universal’nyîe perebornyîe zadachi (Universal search problems, in Russian),Problemy Peredachi Informatsii 9 (1973), 265-266. A corrected English translation appears in an appendix to Trakhtenbrot [39].
[28] R. Lipton, New directions in testing, inProceedings of the DIMACS Workshop on Distributed Computing and Cryptography, 1989, to appear.
[29] C. Lund, L. Fortnow, H. Karloff, and N. Nisan, Algebraic methods for interactive proof systems, inProc. 31st Ann. IEEE Symp. Foundations of Comp. Sci., 1990, 1-10.
[30] P. Orponen, Complexity Classes of Alternating Machines with Oracles,Proc. 10th ICALP, Lecture Notes in Comp. Sci. 154 (1983), 573-584. · Zbl 0521.68043
[31] C. Papadimitriou, Games against Nature,Proc. 24th Ann. IEEE Symp. Foundations of Comp. Sci., 1983, 446-450.
[32] G. Peterson and J. Reif, Multiple-person alternation,Proc. 20th Ann. IEEE Symp. Foundations of Comp. Sci., 1979, 348-363.
[33] M. Santha, Relativized Arthur-Merlin versus Merlin-Arthur games,Inf. and Computation 80 (1989), 44-49. · Zbl 0667.03031
[34] J. Seiferas, M. Fischer, andA. Meyer, Separating Nondeterministic Time Complexity ClassesJ. Assoc. Comput. Mach. 25 (1978), 146-167. · Zbl 0366.68038
[35] A. Shamir, IP=PSPACE, inProc. 31st Ann. IEEE Symp. Foundations of Comp. Sci., 1990, 11-15.
[36] J. Simon, On Some Central Problems in Computational Complexity, Ph.D. Thesis,Cornell University, Computer Science, Tech. Report TR 74-224, 1975.
[37] J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities,J. Assoc. Comput. Mach. 27 (1980), 701-717. · Zbl 0452.68050
[38] M. Szegedy, EfficientMIP protocol and a stronger condition on clique approximation, in preparation.
[39] B. A. Trakhtenbrot, A survey of Russian approaches toPerebor (brute-force search) algorithms,Annals of the History of Computing 6 (1984), 384-400. · Zbl 05085026
[40] S. Toda, On the computational power ofPP and ?P, inProc. 30th Ann. IEEE Symp. Foundations of Comp. Sci., 1989, 514-519.
[41] L. Valiant, The complexity of computing the permanent,Theoretical Computer Science 8 (1979), 189-201. · Zbl 0415.68008
[42] L. Valiant, V. Vazirani,N P is as Easy as Detecting Unique Solutions,Theoretical Computer Science 47 (1986), 85-93. · Zbl 0621.68030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.