Nondeterminisic sublinear time has measure 0 in P

Abstract: The measure hypothesis is a quantitative strengthening of the P != 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.

Review text

In [\textit{J. Cai} et al., ``Constant-depth circuits and the Lutz hypothesis, in: Proceedings of the 38th symposium on foundations of computer science, FOCS 1997. Los Alamitos, CA: IEEE Computer Society. 595--604 (1997)] it is proved that \(\mathrm{NTIME}[n^{1/11}]\) has measure 0 in P. This implies the analogue of the measure hypothesis in P fails, because \(\mathrm{NTIME}[\log n]\) has measure 0 in P. (The measure hypothesis is a quantitative strengthening of the \(\mathrm{P}\not=\mathrm{NP}\) conjecture which asserts that NP is a non-negligible subset of EXP.) \par In the paper under review the authors improve this result by showing that the class of all languages that can be decided in nondeterministic time at most \(n(1-\frac{2\lg\lg n}{\lg n})\) has measure 0 in P. In particular, the nondeterministic sublinear time class \(\mathrm{NTIME}[o(n)]\) has measure 0 in P.

Recommendations

Cites work

Cited in

(1)

BPP has subexponential time simulations unless EXPTIME has publishable proofs

Describes a project that uses

Uses Software

JBool

This page was built for publication: Nondeterminisic sublinear time has measure 0 in P

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1999993)