On the polynomial IO-complexity (Q582102): Difference between revisions
From MaRDI portal
Changed an Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 07:38, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the polynomial IO-complexity |
scientific article |
Statements
On the polynomial IO-complexity (English)
0 references
1989
0 references
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.
0 references
IO-complexity
0 references
sparseness
0 references
P
0 references
NP
0 references
density
0 references
E
0 references
NE
0 references
tally sets
0 references