×

Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. (English) Zbl 0652.03029

Exceedingly long proofs or computer-assisted proofs address the question that there might be a positive probability that a proof is in error. Such facts emphasize the role played in mathematics by the verifier (vs. the prover). The paper deals with the problem of formalization of the notion of efficient provability by overwhelming statistical evidence. A randomized proof combines the nondeterministic nature of a classical proof system with the randomization performed by probabilistic algorithms. The main example is Arthur-Merlin protocol which is used to obtain a hierarchy of complexity classes “just above NP”.
Reviewer: C.Calude

MSC:

03D15 Complexity of computation (including implicit computational complexity)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aiello, W.; Goldwasser, S.; Hastad, J., On the power of interaction, (Proceedings, 27th IEEE Symp. Found. of Comput. Sci. (1986)), 368-379, Full version to appear in Combinatorica
[2] Adleman, L., Two theorems on random polynomial time, (Proceedings, 19th IEEE Symp. Found. of Comput. Sci. (1978)), 75-83
[3] Babai, L., Trading group theory for randomness, (Proceedings, 17th ACM Symp. on Theory of Comput.. Proceedings, 17th ACM Symp. on Theory of Comput., Providence, RI (1985)), 421-429
[4] L. Babai, Interactive proofs in finite groups, in “Randomness and complexity” (S. Micali and F. Preparata, Eds.), to appear.; L. Babai, Interactive proofs in finite groups, in “Randomness and complexity” (S. Micali and F. Preparata, Eds.), to appear. · Zbl 0741.68047
[5] Babai, L.; Erdös, P., Representation of group elements as short products, (Rosa, A.; etal., Theory and Practice of Combinatorics. Theory and Practice of Combinatorics, Annals of Discrete Math., Vol. 12 (1982), North Holland: North Holland Amsterdam), 27-30 · Zbl 0485.00006
[6] Babai, L.; Frankl, P.; Simon, J., Complexity classes in communication complexity theory, (Proceedings, 27th IEEE Symp. Found. of Comput. Sci. (1986)), 337-347
[7] Babai, L.; Luks, E. M., Canonical labeling of graphs, (Proceedings, 15th ACM Symp. Theory of Comput. (1983)), 171-183
[8] L. Babai, E. M. Luks, and E. Szemerédi, On the complexity of matrix group problems, in preparation.; L. Babai, E. M. Luks, and E. Szemerédi, On the complexity of matrix group problems, in preparation.
[9] Babai, L.; Szemerédi, E., On the complexity of matrix group problems, (preliminary version), (Proceedings, 25th IEEE Symp. Found. of Comput. Sci.. Proceedings, 25th IEEE Symp. Found. of Comput. Sci., Palm Beach, FL (1984)), 229-240
[10] Bennett, C. H.; Gill, J., Relative to a random oracle A, \(P^A\) ≠ \(NP^A\) ≠3 co \(NP^A\) with probability 1, SIAM J. Comput., 10, 96-113 (1981) · Zbl 0454.68030
[11] R. Boppana, J. Hastad, and S. Zachos, Does coNP have short interactive proofs? Inform. process. Lett. in press.; R. Boppana, J. Hastad, and S. Zachos, Does coNP have short interactive proofs? Inform. process. Lett. in press. · Zbl 0653.68037
[12] Carter, J. L.; Wegman, M. N., Universal classes of hash functions, J. Comput. System Sci., 18, No. 2, 143-154 (1979) · Zbl 0412.68090
[13] Chandra, A.; Kozen, D.; Stockmeyer, L., Alternation, J. Assoc. Comput. Mach., 28, 114-133 (1981) · Zbl 0473.68043
[14] S.A. Cook, The complexity of theorem proving procedures, in “Proceedings, 3rd ACM Symp. Theory of Comput.”, pp. 151-158.; S.A. Cook, The complexity of theorem proving procedures, in “Proceedings, 3rd ACM Symp. Theory of Comput.”, pp. 151-158. · Zbl 0253.68020
[15] L. Fortnow and M. Sipser, private communication.; L. Fortnow and M. Sipser, private communication.
[16] Furst, M. L.; Hopcroft, J.; Luks, E. M., Polynomial-time algorithms for permutation groups, (Proceedings, 21st IEEE Symp. Found. of Comput. Sci.. Proceedings, 21st IEEE Symp. Found. of Comput. Sci., Syracuse, NY (1980)), 36-41
[17] Gaber, O.; Galil, Z., Explicit construction of linear sized superconcentrators, J. Comput. System Sci., 22, 407-420 (1981) · Zbl 0487.05045
[18] Garey, M.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Competeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[19] Gill, J., Computational complexity of probabilistic Turing machines, SIAM J. Comput., 6, 675-695 (1977) · Zbl 0366.02024
[20] Goldreich, O.; Micali, S.; Wigderson, A., Proofs that yield nothing but their validity and a methodology of cryptographic protocol design, (27th IEEE Symp. Found. of Comput. Sci. (1986)), 174-187
[21] Goldwasser, S.; Micalt, S.; Rackoff, C., The knowledge complexity of interactive proofs, (Proceedings, 17th ACM Symp. Theory of Comput.. Proceedings, 17th ACM Symp. Theory of Comput., Providence, RI (198)), 291-304 · Zbl 0900.94025
[22] Goldwasser, S.; Sipser, M., Private coins versus public coins in interactive proof systems, (Proceedings, 18th ACM Symp. Theory of Comput.. Proceedings, 18th ACM Symp. Theory of Comput., Berkeley, CA (1986)), 59-68
[23] Kurtz, S. A., Randomness and Genericity in the Degrees of Unsolvability, (Ph.D. thesis (1981), Univ. of Illinois at Urbana)
[24] S. A. Kurtz, A note on randomized polynomial time, SIAM J. Comput., in press.; S. A. Kurtz, A note on randomized polynomial time, SIAM J. Comput., in press. · Zbl 0634.68041
[25] Lauremann, C., BPP and the polynomial hierarchy, Inform. Process. Lett., 17, No. 4, 215-217 (1983) · Zbl 0515.68042
[26] Luks, E. M., Isomorphism of graphs of bounded valence can be tested in polynomial time, J. Comput. System Sci., 25, 42-65 (1982) · Zbl 0493.68064
[27] E. M. Luks, The complexity of fixed valence graph isomorphism and the implications for general graph isomorphism, in preparation.; E. M. Luks, The complexity of fixed valence graph isomorphism and the implications for general graph isomorphism, in preparation.
[28] Margulis, G. A., Problems Inform. Transmission, 325-332 (1975), English transl. · Zbl 0336.57037
[29] Meyer, A. R.; Stockmeyer, L. J., The equivalence problem for regular expressions with squaring requires exponential time, (Proceedings, IEEE Annu. Symp. Switching and Automata Theory (1972)), 125-129
[30] Miller, G. L., Riemann’s hypothesis and tests for primality, J. Comput. System Sci., 13, 300-317 (1976) · Zbl 0349.68025
[31] Papadimitriou, C. H., Games against nature, (Proceedings, 24th IEEE Symp. Found. of Comput. Sci.. Proceedings, 24th IEEE Symp. Found. of Comput. Sci., Tucson, AZ (1983)), 446-450
[32] Pinsker, M., On the complexity of a concentrator, (7th Internat. Teletraffic Conf.. 7th Internat. Teletraffic Conf., Stockholm (1973)), 1-4
[33] Pippenger, N., Superconcentrators, (SIAM J. Comput., 6 (1977)), 298-304 · Zbl 0361.05035
[34] Rényi, A., Probability Theory (1976), North-Holland · Zbl 0217.13502
[35] Sacks, G. E., Degrees of unsolvability, (Annals of Math. Studies, Vol. 55 (1966), Princeton Univ. Press: Princeton Univ. Press Princeton, NJ) · Zbl 0118.25202
[36] M. Santha, Relativized Arthur-Merlin versus Merlin-Arthur games, Information and Computation, to appear.; M. Santha, Relativized Arthur-Merlin versus Merlin-Arthur games, Information and Computation, to appear. · Zbl 0644.68053
[37] Santha, M.; Vazirani, U. V., Generating quasi-random sequences from semi-random sources, J. Comput. System Sci., 33, 75-87 (1986) · Zbl 0612.94004
[38] Sims, C. C., Some group theoretic algorithms, (Lecture Notes in Math., Vol. 697 (1978), Springer-Verlag: Springer-Verlag New York), 108-124 · Zbl 0405.20001
[39] Sipser, M., A complexity theoretic approach to randomness, (Proceedings, 15th ACM Symp. Theory of Comput.. Proceedings, 15th ACM Symp. Theory of Comput., Boston (1983)), 330-335
[40] Solovay, R.; Strassen, V., A fast Monte Carlo test for primality, SIAM J. Comput., 6, 84-85 (1977) · Zbl 0345.10002
[41] Stockmeyer, L., The polynomial time hierarchy, Theoret. Comput. Sci., 3, No. 1, 1-22 (1976) · Zbl 0353.02024
[42] Stockmeyer, L., The complexity of approximate counting, (Proceedings, 15th ACM Symp. Theory of Comput. (1983)), 118-126
[43] Vazirani, U. V.; Vazirani, V. V., Random polynomial time is equal to semi-random polynomial time, (Proceedings, 26th IEEE Symp. Found. of Comput. Sci. (1985)), 417-428
[44] Whitehead, A. N.; Russell, B., Principia Mathematica (1927), Cambridge Univ. Press: Cambridge Univ. Press London
[45] S. Zachos and M. Furer, Probabilistic quantifiers vs distrustful adversaries, to appear.; S. Zachos and M. Furer, Probabilistic quantifiers vs distrustful adversaries, to appear. · Zbl 0647.68052
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.