A hierarchy for nondeterministic time complexity

DOI10.1016/S0022-0000(73)80028-5zbMath0278.68042MaRDI QIDQ1394124

Stephen A. Cook

Publication date: 1973

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Relationships between nondeterministic and deterministic tape complexities
• Two-Tape Simulation of Multitape Turing Machines
• A Note Concerning Nondeterministic Tape Complexities

Related Items (34)

Universal quantifiers and time complexity of random access machines ⋮ Classification of the index sets of low \([n^ p\) and high \([n]^ p\)] ⋮ Nonlevelable sets and immune sets in the accepting density hierarchy inNP ⋮ Time hierarchies for cryptographic function inversion with advice ⋮ First-order spectra with one binary predicate ⋮ Local reduction ⋮ Separating classes in the exponential-time hierarchy from classes in PH ⋮ Separating NE from Some Nonuniform Nondeterministic Complexity Classes ⋮ Graph properties checkable in linear time in the number of vertices ⋮ On the Variable Hierarchy of First-Order Spectra ⋮ Hierarchy of complexity of computation of partial functions with values 0 and 1 ⋮ Classifying the computational complexity of problems ⋮ Complexity results for classes of quantificational formulas ⋮ Bounded query machines: on NP and PSPACE ⋮ Separating NE from some nonuniform nondeterministic complexity classes ⋮ Descriptive complexity of \#P functions: a new perspective ⋮ Depth Reduction for Composites ⋮ Towards separating nondeterminism from determinism ⋮ Comparing complexity classes ⋮ Structure in average case complexity ⋮ Techniques for separating space complexity classes ⋮ Toward a mathematical theory of graph-generative systems and its applications ⋮ Bounded-depth succinct encodings and the structure they imply on graphs ⋮ Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ Almost-everywhere complexity hierarchies for nondeterministic time ⋮ Cook reducibility is faster than Karp reducibility in NP ⋮ Alternating time versus deterministic time: A separation ⋮ A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes ⋮ Complexity lower bounds for machine computing models ⋮ Complexity classes and theories of finite models ⋮ A time lower bound for satisfiability ⋮ Unifying known lower bounds via geometric complexity theory ⋮ Average-case rigidity lower bounds

This page was built for publication: A hierarchy for nondeterministic time complexity