Computer Science

Non-deterministic exponential time has two-prover interactive protocols

L. Babai, L. Fortnow, C. Lund

2005COMPUTATIONAL COMPLEXITY

DOI: 10.1007/bf01200056

tlooto Summary

It is shown that the class of languages having tow-prover interactive proof systems is nondeterministic exponential time and that to prove membership in languages inEXP, the honest provers need the power ofEXP only.

Abstract

Abstract is not available.

Citation format

BABAI, L.; FORTNOW, L.; LUND, C. Non-deterministic exponential time has two-prover interactive protocols. COMPUTATIONAL COMPLEXITY, 2005, 1: 3–40.