A Turing machine time hierarchy

DOI10.1016/0304-3975(83)90015-4MaRDI QIDQ593780zbMATH OpenOpenAlexWikidataFDO

Authors Stanislav Zak

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

zbMATH Keywords

complexity hierarchydiagonalizationlanguages over a single-letter alphabetmodified time complexity measuremulti-tape nondeterministic Turing machinesnondeterminismTuring machine computationsuniversal machineunpadding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

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

(28)

• Almost-everywhere complexity hierarchies for nondeterministic time
• Some properties of sets tractable under every polynomial-time computable distribution
• On P-immunity of exponential time complete sets
• Space hierarchy theorem revised.
• Local reduction
• Catalytic space: non-determinism and hierarchy
• Verifying whether one-tape Turing machines run in linear time
• Average-case rigidity lower bounds
• NEXP does not have non-uniform quasipolynomial-size ACC circuits of o( n) depth
• An application of the translational method
• On the cutting edge of relativization: the resource bounded injury method
• Alternating time versus deterministic time: A separation
• Lower bounds against weakly-uniform threshold circuits
• Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
• scientific article; zbMATH DE number 7250146 (Why is no real title available?)
• Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
• Language classes associated with automata over matrix groups
• Efficient Construction of Rigid Matrices Using an NP Oracle
• Effective guessing has unlikely consequences
• A note on uniform circuit lower bounds for the counting hierarchy (extended abstract)
• Rigid matrices from rectangular PCPs
• Efficient construction of rigid matrices using an NP oracle
• Nondeterministic quasi-polynomial time is average-case hard for \textsf{ACC} circuits
• Oblivious complexity classes revisited: lower bounds and hierarchies
• A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
• Time hierarchies for cryptographic function inversion with advice
• Relations between average-case and worst-case complexity
• Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs

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)