Almost-everywhere complexity hierarchies for nondeterministic time
From MaRDI portal
Publication:1261465
DOI10.1016/0304-3975(93)90117-CzbMath0779.68032OpenAlexW2079357831MaRDI QIDQ1261465
Richard Beigel, Eric W. Allender, Homer, Steven, Ulrich Hertrampf
Publication date: 16 September 1993
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(93)90117-c
immunitycomplexity hierarchynondeterministic timenondeterministic Turing machinesalmost-everywhere complexity
Related Items
A note on uniform circuit lower bounds for the counting hierarchy (extended abstract) ⋮ Almost-everywhere superiority for quantum polynomial time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Turing machine time hierarchy
- A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
- Data structures for distributed counting
- Strong nondeterministic polynomial-time reducibilities
- A note on arbitrarily complex recursive functions
- A hierarchy for nondeterministic time complexity
- Time bounded random access machines
- Time- and tape-bounded Turing acceptors and AFLs
- Bi-immune sets for complexity classes
- Limitations on Separating Nondeterministic Complexity Classes
- Separating Nondeterministic Time Complexity Classes
- On the Computational Complexity of Algorithms
- Two-Tape Simulation of Multitape Turing Machines
