Non-deterministic exponential time has two-prover interactive protocols
- 1 March 1991
- journal article
- research article
- Published by Springer Nature in computational complexity
- Vol. 1 (1), 3-40
- https://doi.org/10.1007/bf01200056
Abstract
No abstract availableKeywords
This publication has 28 references indexed in Scilit:
- E-mail and the unexpected power of interactionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Arithmetization: A new method in structural complexity theorycomputational complexity, 1991
- Checking computations in polylogarithmic timePublished by Association for Computing Machinery (ACM) ,1991
- Self-testing/correcting with applications to numerical problemsPublished by Association for Computing Machinery (ACM) ,1990
- Hiding instances in multioracle queriesLecture Notes in Computer Science, 1990
- Designing programs that check their workPublished by Association for Computing Machinery (ACM) ,1989
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classesJournal of Computer and System Sciences, 1988
- Multi-prover interactive proofs: how to remove intractabilityPublished by Association for Computing Machinery (ACM) ,1988
- On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated AnnealingProbability in the Engineering and Informational Sciences, 1987
- Trading group theory for randomnessPublished by Association for Computing Machinery (ACM) ,1985