Nondeterminisic Sublinear Time Has Measure 0 in P
| Autor: | John M. Hitchcock, Adewale Sekoni |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
FOS: Computer and information sciences
Class (set theory) Conjecture NTIME Sublinear time Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Computational Complexity (cs.CC) Measure (mathematics) Theoretical Computer Science Decidability Combinatorics Nondeterministic algorithm Computer Science - Computational Complexity Computational Theory and Mathematics Theory of computation Mathematics |
| Popis: | The measure hypothesis is a quantitative strengthening of the $\mathrm {P} \neq \text {NP}$ conjecture which asserts that $\text {NP}$ is a nonnegligible subset of $\text {EXP}$ . Cai et al. (1997) showed that the analogue of this hypothesis in $\mathrm {P}$ is false. In particular, they showed that $\text {NTIME}[n^{1/11}]$ has measure 0 in $\mathrm {P}$ . We improve on their result to show that the class of all languages decidable in nondeterministic sublinear time has measure 0 in $\mathrm {P}$ . Our result is based on DNF width and holds for all four major notions of measure on $\mathrm {P}$ . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|