Nondeterminisic sublinear time has measure 0 in P. (English) Zbl 1459.68076
In [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.)
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.
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.
Reviewer: Marat M. Arslanov (Kazan)
MSC:
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 68Q45 | Formal languages and automata |
Software:
JBoolReferences:
| [1] | Allender, E., Rubinstein, R.: P-printable sets. SIAM J. Comput. 17, 1193-1202 (1988) · Zbl 0682.68039 · doi:10.1137/0217075 |
| [2] | Allender, E., Strauss, M.: Measure on small complexity classes with applications for BPP. In: Proceedings of the 35th Symposium on Foundations of Computer Science, pp. 807-818. IEEE Computer Society (1994) |
| [3] | Allender, E., Strauss, M.: Measure on P Robustness of the notion. In: International Symposium on Mathematical Foundations of Computer Science, pp. 129-138. Springer (1995) · Zbl 1193.68111 |
| [4] | Ambos-Spies, K., Mayordomo, E.: Resource-bounded measure and randomness. In: Sorbi, A. (ed.) Complexity, Logic and Recursion Theory, Lecture Notes in Pure and Applied Mathematics, pp 1-47. Marcel Dekker, New York (1997) · Zbl 0877.68055 |
| [5] | Cai, J., Sivakumar, D., Strauss, M.: Constant-depth circuits and the Lutz hypothesis. In: Proceedings of the 38th Symposium on Foundations of Computer Science, pp. 595-604. IEEE Computer Society (1997) |
| [6] | Crama, Y., Hammer, P.L.: Boolean Functions - Theory, Algorithms, and Applications, volume 142 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press (2011) |
| [7] | Lutz, J.H.: Almost everywhere high nonuniform complexity. J. Comput. Syst. Sci. 44(2), 220-258 (1992) · Zbl 0767.68043 · doi:10.1016/0022-0000(92)90020-J |
| [8] | Lutz, J.H.: The quantitative structure of exponential time. In: Hemaspaandra, L.A., Selman, A.L. (eds.) Complexity Theory Retrospective II, pp 225-254. Springer (1997) · Zbl 0880.68044 |
| [9] | Lutz, J.H.: Dimension in complexity classes. SIAM J. Comput. 32(5), 1236-1259 (2003) · Zbl 1026.68059 · doi:10.1137/S0097539701417723 |
| [10] | Lutz, J.H., Mayordomo, E.: Cook versus Karp-Levin: Separating completeness notions if NP is not small. Theor. Comput. Sci. 164(1-2), 141-163 (1996) · Zbl 0871.68083 · doi:10.1016/0304-3975(95)00189-1 |
| [11] | Lutz, J.H., Mayordomo, E.: Twelve problems in resource-bounded measure. Bull. European Assoc. Theor. Comput. Sci. 68, 64-80 (1999). Also in Current Trends in Theoretical Computer Science: Entering the 21st Century, pages 83-101 World Scientific Publishing, 2001 · Zbl 0936.68049 |
| [12] | Moser, P.: Martingale families and dimension in P. Theor. Comput. Sci. 400 (1-3), 46-61 (2008) · Zbl 1144.68026 · doi:10.1016/j.tcs.2008.02.013 |
| [13] | O’Donnell, R.: Analysis of Boolean Functions. Cambridge University Press (2014) · Zbl 1336.94096 |
| [14] | Strauss, M.: Measure on P: Strength of the notion. Inf. Comput. 136(1), 1-23 (1997) · Zbl 0874.68175 · doi:10.1006/inco.1997.2639 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
