On average time hierarchies

DOI10.1016/0020-0190(94)90048-5zbMath0787.68040OpenAlexW2066875791WikidataQ56959109 ScholiaQ56959109MaRDI QIDQ1313704

Per Grape, Mikael Goldmann, Johan T. Håstad

Publication date: 24 February 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)90048-5

zbMATH Keywords

computational complexityhierarchy theoremsaverage time hierarchyaverage time-complexityhierarchy for functions

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

No NP problems averaging over ranking of distributions are harder ⋮ Worst-Case to Average-Case Reductions for Subclasses of P ⋮ Rankable distributions do not provide harder instances than uniform distributions ⋮ Reductions and convergence rates of average time

Cites Work

• Unnamed Item
• Unnamed Item
• The foundations of mathematics. A study in the philosophy of science
• Average case completeness
• Average Case Complete Problems
• On the Computational Complexity of Algorithms
• Two-Tape Simulation of Multitape Turing Machines
• A Machine-Independent Theory of the Complexity of Recursive Functions

This page was built for publication: On average time hierarchies