Nondeterminisic sublinear time has measure 0 in P (Q1999993)

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.