Translational lemmas, polynomial time, and ( n)^j-space
From MaRDI portal
(Redirected from Publication:1225932)
Translational lemmas, polynomial time, and \((\log n)^j\)-space
Translational lemmas, polynomial time, and \((\log n)^j\)-space
Cites work
- A Note Concerning Nondeterministic Tape Complexities
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Comparing complexity classes
- scientific article; zbMATH DE number 3562523 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- scientific article; zbMATH DE number 3363526 (Why is no real title available?)
- scientific article; zbMATH DE number 3407150 (Why is no real title available?)
- On Languages Accepted in Polynomial Time
- On the Computational Complexity of Algorithms
- Relationships between nondeterministic and deterministic tape complexities
- The complexity of theorem-proving procedures
- The Hardest Context-Free Language
Cited in
(11)- Optimization problems and the polynomial hierarchy
- Symmetric space-bounded computation
- 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
- scientific article; zbMATH DE number 3808971 (Why is no real title available?)
- Classifying the computational complexity of problems
- Inclusion complete tally languages and the Hartmanis-Berman conjecture
- scientific article; zbMATH DE number 3576701 (Why is no real title available?)
This page was built for publication: Translational lemmas, polynomial time, and \((\log n)^j\)-space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1225932)
