Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- 1 April 1988
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 36 (2) , 254-276
- https://doi.org/10.1016/0022-0000(88)90028-1
Abstract
No abstract availableThis publication has 28 references indexed in Scilit:
- Generating quasi-random sequences from semi-random sourcesJournal of Computer and System Sciences, 1986
- BPP and the polynomial hierarchyInformation Processing Letters, 1983
- Isomorphism of graphs of bounded valence can be tested in polynomial timeJournal of Computer and System Sciences, 1982
- Explicit constructions of linear-sized superconcentratorsJournal of Computer and System Sciences, 1981
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1SIAM Journal on Computing, 1981
- AlternationJournal of the ACM, 1981
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979
- Some group-theoretic algorithmsLecture Notes in Mathematics, 1978
- Riemann's hypothesis and tests for primalityJournal of Computer and System Sciences, 1976
- The polynomial-time hierarchyTheoretical Computer Science, 1976