On relationships between complexity classes of Turing machines

DOI10.1134/S096554251704011XzbMath1382.68085OpenAlexW2615658319MaRDI QIDQ1682916

V. N. Zakharov, V. A. Kozmidiadi

Publication date: 6 December 2017

Published in: Computational Mathematics and Mathematical Physics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s096554251704011x

zbMATH Keywords

computational complexitypolynomial reducibilitydeterministic Turing machinesnondeterministic Turing machines\(\mathrm{DSPACE}(|X|^n)\) vs \(\mathrm{NSPACE}(|X|^n)\)Karp reducibilityNP-complete Turing machinesP vs NP problem

Mathematics Subject Classification ID

Uses Software

• MathOverflow

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Relationships between nondeterministic and deterministic tape complexities
• On the Structure of Polynomial Time Reducibility
• On Time Versus Space
• Separating Nondeterministic Time Complexity Classes
• Reducibility among Combinatorial Problems
• On the Computational Complexity of Algorithms
• The complexity of theorem-proving procedures

This page was built for publication: On relationships between complexity classes of Turing machines