Translational lemmas, polynomial time, and \((\log n)^j\)-space

DOI10.1016/0304-3975(76)90057-8zbMath0326.68030OpenAlexW1968954131WikidataQ124840365 ScholiaQ124840365MaRDI QIDQ1225932

Ronald V. Book

Publication date: 1976

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(76)90057-8

Mathematics Subject Classification ID

Related Items (11)

Unnamed Item ⋮ Optimization problems and the polynomial hierarchy ⋮ Classifying the computational complexity of problems ⋮ Symmetric space-bounded computation ⋮ Unnamed Item ⋮ Inclusion complete tally languages and the Hartmanis-Berman conjecture ⋮ Remarks on the complexity of nondeterministic counter languages ⋮ On the complexity of formal grammars ⋮ Stack languages and log n space ⋮ A positive relativization of polynomial time versus polylog space ⋮ The ancestor width of grammars and languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Comparing complexity classes
• Relationships between nondeterministic and deterministic tape complexities
• The Hardest Context-Free Language
• On the Computational Complexity of Algorithms
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• On Languages Accepted in Polynomial Time
• A Note Concerning Nondeterministic Tape Complexities
• The complexity of theorem-proving procedures

This page was built for publication: Translational lemmas, polynomial time, and \((\log n)^j\)-space