zbMATH — the first resource for mathematics

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
Full Text:
References:
 [1] Aiello, W.; Goldwasser, S.; Hastad, J., On the power of interaction, (), 368-379, Full version to appear in Combinatorica [2] Adleman, L., Two theorems on random polynomial time, (), 75-83 [3] Babai, L., Trading group theory for randomness, (), 421-429 [4] {\scL. 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, (), 27-30 [6] Babai, L.; Frankl, P.; Simon, J., Complexity classes in communication complexity theory, (), 337-347 [7] Babai, L.; Luks, E.M., Canonical labeling of graphs, (), 171-183 [8] {\scL. 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), (), 229-240 [10] Bennett, C.H.; Gill, J., Relative to a random oracle A, P^{A} ≠ NPA ≠3 conpa with probability 1, SIAM J. comput., 10, 96-113, (1981) · Zbl 0454.68030 [11] {\scR. Boppana, J. Hastad, and S. Zachos}, Does coNP have short interactive proofs? Inform. process. Lett. in press. [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] {\scS.A. Cook}, The complexity of theorem proving procedures, in “Proceedings, 3rd ACM Symp. Theory of Comput.”, pp. 151-158. [15] {\scL. Fortnow and M. Sipser}, private communication. [16] Furst, M.L.; Hopcroft, J.; Luks, E.M., Polynomial-time algorithms for permutation groups, (), 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 San Francisco [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, (), 174-187 [21] Goldwasser, S.; Micalt, S.; Rackoff, C., The knowledge complexity of interactive proofs, (), 291-304 · Zbl 0900.94025 [22] Goldwasser, S.; Sipser, M., Private coins versus public coins in interactive proof systems, (), 59-68 [23] Kurtz, S.A., Randomness and genericity in the degrees of unsolvability, () [24] {\scS. 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] {\scE. M. Luks}, The complexity of fixed valence graph isomorphism and the implications for general graph isomorphism, in preparation. [28] Margulis, G.A.; Margulis, G.A., Explicit constructions of concentrators, Problemy. peredachi informatsii, Problems inform. transmission, 9, 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, (), 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, (), 446-450 [32] Pinsker, M., On the complexity of a concentrator, (), 1-4 [33] Pippenger, N., Superconcentrators, (), 298-304 · Zbl 0361.05035 [34] Rényi, A., Probability theory, (1976), North-Holland · Zbl 0217.13502 [35] Sacks, G.E., Degrees of unsolvability, () · Zbl 0118.25202 [36] {\scM. 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, (), 108-124 [39] Sipser, M., A complexity theoretic approach to randomness, (), 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, (), 118-126 [43] Vazirani, U.V.; Vazirani, V.V., Random polynomial time is equal to semi-random polynomial time, (), 417-428 [44] Whitehead, A.N.; Russell, B.; Whitehead, A.N.; Russell, B., Principia Mathematica, (1927), Cambridge Univ. Press London · JFM 53.0038.02 [45] {\scS. 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. 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.