On the polynomial IO-complexity
type: Item
instance of: scholarly article
title: On the polynomial IO-complexity
zbMATH Open document ID: 0689.68069
DOI: 10.1016/0020-0190(89)90141-5
author: José Rolim
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: We want to know the relationship between the class P and NP and the new defined classes P(d(n)) and NP(d(n)). We show that there exists a positive density function d(n) for which P(d(n))\(\neq NP(d(n))\) if and only if \(P\neq NP\). On the other hand, we also show that the existence of a positive density function d(n) for which \(P(d(n))=NP(d(n))\) implies that \(E=NE\), where E is the deterministic exponential class and NE is the non-deterministic exponential class of languages. Using the concept of density function, we give an alternative proof that NE\(\neq E\) implies NP\(\neq P\). The implication NE\(\neq E\) implies NP\(\neq P\) was already known. This was showed using the concept of tally sets by Book, and using the concept of sparse sets by Hartmanis.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 4130021
zbMATH Keywords: IO-complexity
zbMATH Keywords: sparseness
zbMATH Keywords: P
zbMATH Keywords: NP
zbMATH Keywords: density
zbMATH Keywords: E
zbMATH Keywords: NE
zbMATH Keywords: tally sets
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90141-5
OpenAlex ID: W2009806555
cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
cites work: On Effective Procedures for Speeding Up Algorithms
cites work: Tally languages and complexity classes
cites work: On sparse sets in NP-P
cites work: Sparse sets in NP-P: EXPTIME versus NEXPTIME
cites work: Completeness, Approximation and Density
cites work: On the IO-complexity and approximation languages
cites work: A note on the best-case complexity
description: scientific article; zbMATH DE number 4130021