A comparison of polynomial time completeness notions
type: Item
instance of: scholarly article
title: A comparison of polynomial time completeness notions
zbMATH Open document ID: 0635.68035
DOI: 10.1016/0304-3975(87)90132-0
author: Osamu Watanabe
published in: Theoretical Computer Science
publication date: 1987-01-01T00:00:00Z
review text: Several types of polynomial time reductions for the superpolynomial decision problem class \(DEXT=\cup \{DTIME(2^{cn})|\) \(c>0\}\) are considered. The purpose of the paper is to characterize the differences between polynomial time completeness notions for DEXT with respect to any pair of the above reductions. The author succeeds to prove all but two differences for the class DEXT. An interesting open problem is whether or not the obtained results hold also for complexity classes specified by nondeterministic machines.
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4035136
zbMATH Keywords: polynomial time transformation
zbMATH Keywords: superpolynomial deterministic classes
zbMATH Keywords: polynomial time reductions
zbMATH Keywords: superpolynomial decision problem class
zbMATH Keywords: completeness
zbMATH Keywords: complexity classes
Wikidata QID: Q56387788
MaRDI profile type: Publication
full work available at URL: 0304-3975(87)90132-0
OpenAlex ID: W2068655609
cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
cites work: Bi-immune sets for complexity classes
cites work: Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: Qualitative relativizations of complexity classes
cites work: The complexity of theorem-proving procedures
cites work: Q4162663
cites work: Q3862379
cites work: Completeness, Approximation and Density
cites work: A comparison of polynomial time reducibilities
cites work: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
cites work: Q5573961
cites work: On one-one polynomial time equivalence relations
description: scientific article; zbMATH DE number 4035136