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)

Related Items (33)

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 ⋮ 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

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

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