A Turing machine time hierarchy
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 3655356 (Why is no real title available?)
- scientific article; zbMATH DE number 3669861 (Why is no real title available?)
- scientific article; zbMATH DE number 3399206 (Why is no real title available?)
- Real-Time Simulation of Multihead Tape Units
- Separating Nondeterministic Time Complexity Classes
Cited in
(25)- Language classes associated with automata over matrix groups
- A note on uniform circuit lower bounds for the counting hierarchy (extended abstract)
- Average-case rigidity lower bounds
- Time hierarchies for cryptographic function inversion with advice
- Verifying whether one-tape Turing machines run in linear time
- An application of the translational method
- Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs
- scientific article; zbMATH DE number 7250146 (Why is no real title available?)
- Efficient Construction of Rigid Matrices Using an NP Oracle
- Local reduction
- Effective guessing has unlikely consequences
- On the cutting edge of relativization: The resource bounded injury method
- Some properties of sets tractable under every polynomial-time computable distribution
- A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
- Lower bounds against weakly-uniform threshold circuits
- Rigid matrices from rectangular PCPs
- Alternating time versus deterministic time: A separation
- Almost-everywhere complexity hierarchies for nondeterministic time
- Relations between average-case and worst-case complexity
- On P-immunity of exponential time complete sets
- Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
- Catalytic space: non-determinism and hierarchy
- NEXP does not have non-uniform quasipolynomial-size ACC circuits of \(o(\log \log n)\) depth
- Space hierarchy theorem revised.
- Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
This page was built for publication: A Turing machine time hierarchy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q593780)
