Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-013 | 18th January 2018 00:23

Nondeterminisic Sublinear Time Has Measure 0 in P

RSS-Feed




TR18-013
Authors: John Hitchcock, Adewale Sekoni
Publication: 21st January 2018 13:31
Downloads: 806
Keywords: 


Abstract:

The measure hypothesis is a quantitative strengthening of the P $\neq$ NP conjecture which asserts that NP is a nonnegligible subset of EXP. Cai, Sivakumar, and Strauss (1997) showed that the analogue of this hypothesis in P is false. In particular, they showed that NTIME[$n^{1/11}$] has measure 0 in P. We improve on their result to show that the class of all languages decidable in nondeterministic sublinear time has measure 0 in P. Our result is based on DNF width and holds for all four major notions of measure on P.



ISSN 1433-8092 | Imprint