A hierarchy for nondeterministic time complexity

DOI10.1016/S0022-0000(73)80028-5MaRDI QIDQ1394124zbMATH OpenFDO

Authors Stephen Cook

Publication date 1973

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

Full work available at URL https://doi.org/10.1016/S0022-0000(73)80028-5

Mathematics Subject Classification ID

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

Cites work

• A Note Concerning Nondeterministic Tape Complexities
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3407150 (Why is no real title available?)
• Relationships between nondeterministic and deterministic tape complexities
• Two-Tape Simulation of Multitape Turing Machines

Cited in

(34)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1394124)