On relationships between complexity classes of Turing machines
type: Item
instance of: scholarly article
title: On relationships between complexity classes of Turing machines
zbMATH Open document ID: 1382.68085
DOI: 10.1134/S096554251704011X
author: V. N. Zakharov
author: V. A. Kozmidiadi
published in: Computational Mathematics and Mathematical Physics
publication date: 2017-12-06T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 6815874
zbMATH Keywords: P vs NP problem
zbMATH Keywords: \(\mathrm{DSPACE}(|X|^n)\) vs \(\mathrm{NSPACE}(|X|^n)\)
zbMATH Keywords: polynomial reducibility
zbMATH Keywords: Karp reducibility
zbMATH Keywords: NP-complete Turing machines
zbMATH Keywords: computational complexity
zbMATH Keywords: deterministic Turing machines
zbMATH Keywords: nondeterministic Turing machines
describes a project that uses: MathOverflow
MaRDI profile type: Publication
cites work: The complexity of theorem-proving procedures
cites work: Q4071737
cites work: Q3589189
cites work: On the Computational Complexity of Algorithms
cites work: Separating Nondeterministic Time Complexity Classes
cites work: Reducibility among Combinatorial Problems
cites work: On the Structure of Polynomial Time Reducibility
cites work: Q5636862
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: On Time Versus Space
full work available at URL: s096554251704011x
OpenAlex ID: W2615658319
description: scientific article; zbMATH DE number 6815874