A Turing machine time hierarchy
From MaRDI portal
Publication:593780
DOI10.1016/0304-3975(83)90015-4zbMath0525.68026OpenAlexW2144345645WikidataQ55969688 ScholiaQ55969688MaRDI QIDQ593780
Publication date: 1983
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(83)90015-4
diagonalizationnondeterminismcomplexity hierarchylanguages over a single-letter alphabetmodified time complexity measuremulti-tape nondeterministic Turing machinesTuring machine computationsuniversal machineunpadding
Related Items
Time hierarchies for cryptographic function inversion with advice, Some properties of sets tractable under every polynomial-time computable distribution, Local reduction, An application of the translational method, On P-immunity of exponential time complete sets, Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization, Robust simulations and significant separations, Effective guessing has unlikely consequences, Space hierarchy theorem revised., A note on uniform circuit lower bounds for the counting hierarchy (extended abstract), Catalytic space: non-determinism and hierarchy, Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma, Relations between average-case and worst-case complexity, On the cutting edge of relativization: The resource bounded injury method, New algorithms and lower bounds for circuits with linear threshold gates, Lower bounds against weakly-uniform threshold circuits, NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth, Verifying whether one-tape Turing machines run in linear time, Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs, Natural Proofs versus Derandomization, Almost-everywhere complexity hierarchies for nondeterministic time, Unnamed Item, Language classes associated with automata over matrix groups, Alternating time versus deterministic time: A separation, A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes, Efficient Construction of Rigid Matrices Using an NP Oracle, Average-case rigidity lower bounds
Cites Work
