On average time hierarchies

DOI10.1016/0020-0190(94)90048-5MaRDI QIDQ1313704zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Mikael Goldmann, Per Grape, Johan Hastad

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 classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 3878362
• A generic time hierarchy with one bit of advice
• Time hierarchies for sampling distributions
• Time hierarchies for sampling distributions
• Publication:3476799
• Tighter constant-factor time hierarchies
• scientific article; zbMATH DE number 4161821
• Delay and size in hierarchical organizations
• Heuristic time hierarchies via hierarchies for sampling distributions

Cites work

• scientific article; zbMATH DE number 3476588 (Why is no real title available?)
• scientific article; zbMATH DE number 3313427 (Why is no real title available?)
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Average Case Complete Problems
• Average case completeness
• On the Computational Complexity of Algorithms
• The foundations of mathematics. A study in the philosophy of science
• Two-Tape Simulation of Multitape Turing Machines

Cited in

(7)

• No NP problems averaging over ranking of distributions are harder
• Worst-Case to Average-Case Reductions for Subclasses of P
• Structure in average case complexity
• Reductions and convergence rates of average time
• Dimension- and time-hierarchies for small time bounds.
• Rankable distributions do not provide harder instances than uniform distributions
• On proving time constructibility of functions

This page was built for publication: On average time hierarchies

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