On the polynomial IO-complexity (Q582102): Difference between revisions

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.