Two prover protocols
From MaRDI portal
Publication:2817609
DOI10.1145/195058.195128zbMath1345.03106OpenAlexW2090863037MaRDI QIDQ2817609
Publication date: 1 September 2016
Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/195058.195128
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Related Items
Improved non-approximability results for minimum vertex cover with density constraints ⋮ Zero knowledge and the chromatic number ⋮ Interactive and probabilistic proof-checking ⋮ On weighted vs unweighted versions of combinatorial optimization problems
