Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy

DOI10.1007/11830924_36MaRDI QIDQ3595406zbMATH OpenOpenAlexFDO

Authors Dan Gutfreund

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Some Results on Average-Case Hardness Within the Polynomial Hierarchy
• If NP languages are hard on the worst-case, then it is easy to find their hard instances
• Complexity of distributions and average-case hardness
• Average-case intractability vs. worst-case intractability
• scientific article; zbMATH DE number 5081744

Cited in

(5)

• Some Results on Average-Case Hardness Within the Polynomial Hierarchy
• NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES
• scientific article; zbMATH DE number 7758312 (Why is no real title available?)
• Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?
• Constructive separations and their consequences

This page was built for publication: Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3595406)