Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy
From MaRDI portal
Publication:3595406
DOI10.1007/11830924_36zbMath1155.68397OpenAlexW2144537400MaRDI QIDQ3595406
Publication date: 28 August 2007
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11830924_36
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Related Items (3)
Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? ⋮ Unnamed Item ⋮ NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES
This page was built for publication: Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy
