Separating Nondeterministic Time Complexity Classes

DOI10.1145/322047.322061zbMath0366.68038OpenAlexW1996834809WikidataQ55969687 ScholiaQ55969687MaRDI QIDQ4142696

Joel I. Seiferas, Albert R. Meyer, Michael J. Fischer

Publication date: 1978

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322047.322061

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Turing machines and related notions (03D10)

Related Items (46)

Universal quantifiers and time complexity of random access machines ⋮ Nonlevelable sets and immune sets in the accepting density hierarchy inNP ⋮ A logical approach to locality in pictures languages ⋮ Time hierarchies for cryptographic function inversion with advice ⋮ Local reduction ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ An application of the translational method ⋮ On P-immunity of exponential time complete sets ⋮ k\(+1\) heads are better than k for PDAs ⋮ Dominoes and the complexity of subclasses of logical theories ⋮ A Turing machine time hierarchy ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Robust simulations and significant separations ⋮ Unnamed Item ⋮ The minimum oracle circuit size problem ⋮ On relationships between complexity classes of Turing machines ⋮ Space hierarchy theorem revised. ⋮ A note on uniform circuit lower bounds for the counting hierarchy (extended abstract) ⋮ Classifying the computational complexity of problems ⋮ On time-space classes and their relation to the theory of real addition ⋮ Bounded query machines: on NP and PSPACE ⋮ Some results on relativized deterministic and nondeterministic time hierarchies ⋮ A uniform method for proving lower bounds on the computational complexity of logical theories ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ Relations between average-case and worst-case complexity ⋮ Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines ⋮ On the cutting edge of relativization: The resource bounded injury method ⋮ On the definitions of some complexity classes of real numbers ⋮ An improved lower bound for the elementary theories of trees ⋮ Non-deterministic exponential time has two-prover interactive protocols ⋮ Avoiding simplicity is complex ⋮ Towards separating nondeterminism from determinism ⋮ Verifying whether one-tape Turing machines run in linear time ⋮ Techniques for separating space complexity classes ⋮ Bounded-depth succinct encodings and the structure they imply on graphs ⋮ Almost-everywhere complexity hierarchies for nondeterministic time ⋮ Unnamed Item ⋮ Alternating time versus deterministic time: A separation ⋮ A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes ⋮ Some consequences of the existnce of pseudorandom generators ⋮ Sparse sets and collapse of complexity classes ⋮ A time lower bound for satisfiability ⋮ Deterministic two-way one-head pushdown automata are very powerful ⋮ Towards the Actual Relationship Between NP and Exponential Time ⋮ Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines ⋮ Average-case rigidity lower bounds

This page was built for publication: Separating Nondeterministic Time Complexity Classes