A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
From MaRDI portal
Publication:756423
DOI10.1016/0890-5401(91)90022-TzbMath0722.68056OpenAlexW2045334235MaRDI QIDQ756423
John G. Geske, Dung T. Huynh, Joel I. Seiferas
Publication date: 1991
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(91)90022-t
Related Items (8)
Almost every set in exponential time is P-bi-immune ⋮ Reductions and convergence rates of average time ⋮ Relations between average-case and worst-case complexity ⋮ Almost-everywhere complexity hierarchies for nondeterministic time ⋮ Almost every set in exponential time is P-bi-immune ⋮ Complete distributional problems, hard languages, and resource-bounded measure ⋮ Almost-everywhere superiority for quantum polynomial time ⋮ Towards the Actual Relationship Between NP and Exponential Time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Turing machine time hierarchy
- Data structures for distributed counting
- Minimizing access pointers into trees and arrays
- A note on arbitrarily complex recursive functions
- On time hierarchies
- Simulations among multidimensional Turing machines
- A hierarchy for nondeterministic time complexity
- Time bounded random access machines
- Bi-immune sets for complexity classes
- On Almost Everywhere Complex Recursive Functions
- Separating Nondeterministic Time Complexity Classes
- Infinite exponent partition relations and well-ordered choice
- On the Computational Complexity of Algorithms
- Two-Tape Simulation of Multitape Turing Machines
- A Machine-Independent Theory of the Complexity of Recursive Functions
- Computational Complexity of One-Tape Turing Machine Computations
This page was built for publication: A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
