On average time hierarchies
From MaRDI portal
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)