Some Results on Average-Case Hardness Within the Polynomial Hierarchy
From MaRDI portal
Publication:5385985
DOI10.1007/11944836_19zbMath1177.68096OpenAlexW1501939853MaRDI QIDQ5385985
A. Pavan, Rahul Santhanam, N. V. Vinodchandran
Publication date: 17 April 2008
Published in: FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://www.pure.ed.ac.uk/ws/files/17974469/Pavan_Santhanam_ET_AL_2006_Some_Results_on_Average_Case_Hardness_within_the_Polynomial_Hierarchy.pdf
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Unnamed Item, The 1-Versus-2 Queries Problem Revisited, The 1-versus-2 queries problem revisited, Unnamed Item, PAC-learning gains of Turing machines over circuits and neural networks