Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions

DOI10.1145/167088.167190zbMath1310.68085OpenAlexW2019482147MaRDI QIDQ5248499

Joan Feigenbaum, Anne Condon, Peter W. Shor, Carstent Lund

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167190

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (6)

On the longest circuit in an alterable digraph ⋮ The complexity of approximating PSPACE-complete problems for hierarchical specifications ⋮ The complexity of debate checking ⋮ Approximate solution of NP optimization problems ⋮ The relativized relationship between probabilistically checkable debate systems, IP and PSPACE ⋮ Hierarchically specified unit disk graphs

This page was built for publication: Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions