Comparing complexity classes

DOI10.1016/S0022-0000(74)80008-5zbMath0331.02020OpenAlexW1971578307WikidataQ56387787 ScholiaQ56387787MaRDI QIDQ1227731

Ronald V. Book

Publication date: 1974

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(74)80008-5

Mathematics Subject Classification ID

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

Related Items (16)

Some descriptive-set-theoretical problems in complexity theory ⋮ Some formal results about stratificational grammars and their relevance to linguistics ⋮ Expressing uniformity via oracles ⋮ Unnamed Item ⋮ Promise problems complete for complexity classes ⋮ Unnamed Item ⋮ The guarding game is E-complete ⋮ Inclusion complete tally languages and the Hartmanis-Berman conjecture ⋮ Translational lemmas, polynomial time, and \((\log n)^j\)-space ⋮ Remarks on the complexity of nondeterministic counter languages ⋮ Storage requirements for deterministic polynomial time recognizable languages ⋮ Complexity of some problems in Petri nets ⋮ On the complexity of formal grammars ⋮ A note on classes of complements and the LBA-problem ⋮ P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP ⋮ An upward measure separation theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A hierarchy for nondeterministic time complexity
• Relationships between nondeterministic and deterministic tape complexities
• Principal AFL
• A generator of context-sensitive languages
• Time- and tape-bounded Turing acceptors and AFLs
• Tape-bounded Turing acceptors and principal AFLs
• On the Computational Complexity of Algorithms
• Quasi-realtime languages
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• A note on AFLs and bounded erasing
• A Note Concerning Nondeterministic Tape Complexities
• On Languages Accepted in Polynomial Time
• The complexity of theorem-proving procedures

This page was built for publication: Comparing complexity classes