The complexity of the max word problem and the power of one-way interactive proof systems
- 1 September 1993
- journal article
- Published by Springer Nature in computational complexity
- Vol. 3 (3) , 292-305
- https://doi.org/10.1007/bf01271372
Abstract
No abstract availableKeywords
This publication has 16 references indexed in Scilit:
- Approximating clique is almost NP-completePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Proof verification and hardness of approximation problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Space-bounded probabilistic game automataJournal of the ACM, 1991
- Non-deterministic exponential time has two-prover interactive protocolscomputational complexity, 1991
- Checking computations in polylogarithmic timePublished by Association for Computing Machinery (ACM) ,1991
- The complexity of the max word problemPublished by Springer Nature ,1991
- The ring of k-regular sequencesPublished by Springer Nature ,1990
- Trading group theory for randomnessPublished by Association for Computing Machinery (ACM) ,1985
- The knowledge complexity of interactive proof-systemsPublished by Association for Computing Machinery (ACM) ,1985
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977