{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T04:02:35Z","timestamp":1751774555266,"version":"3.41.0"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,6,28]],"date-time":"2018-06-28T00:00:00Z","timestamp":1530144000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s00224-018-9875-0","type":"journal-article","created":{"date-parts":[[2018,6,28]],"date-time":"2018-06-28T05:01:06Z","timestamp":1530162066000},"page":"386-393","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Nondeterminisic Sublinear Time Has Measure 0 in P"],"prefix":"10.1007","volume":"63","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8614-7307","authenticated-orcid":false,"given":"John M.","family":"Hitchcock","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adewale","family":"Sekoni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,28]]},"reference":[{"key":"9875_CR1","doi-asserted-by":"publisher","first-page":"1193","DOI":"10.1137\/0217075","volume":"17","author":"E Allender","year":"1988","unstructured":"Allender, E., Rubinstein, R.: P-printable sets. SIAM J. Comput. 17, 1193\u20131202 (1988)","journal-title":"SIAM J. Comput."},{"key":"9875_CR2","doi-asserted-by":"crossref","unstructured":"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\u2013818. IEEE Computer Society (1994)","DOI":"10.1109\/SFCS.1994.365713"},{"key":"9875_CR3","doi-asserted-by":"crossref","unstructured":"Allender, E., Strauss, M.: Measure on P Robustness of the notion. In: International Symposium on Mathematical Foundations of Computer Science, pp. 129\u2013138. Springer (1995)","DOI":"10.1007\/3-540-60246-1_119"},{"key":"9875_CR4","doi-asserted-by":"crossref","unstructured":"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\u201347. Marcel Dekker, New York (1997)","DOI":"10.1201\/9780429187490-1"},{"key":"9875_CR5","unstructured":"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\u2013604. IEEE Computer Society (1997)"},{"key":"9875_CR6","doi-asserted-by":"crossref","unstructured":"Crama, Y., Hammer, P.L.: Boolean Functions - Theory, Algorithms, and Applications, volume 142 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press (2011)","DOI":"10.1017\/CBO9780511852008"},{"issue":"2","key":"9875_CR7","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"JH Lutz","year":"1992","unstructured":"Lutz, J.H.: Almost everywhere high nonuniform complexity. J. Comput. Syst. Sci. 44(2), 220\u2013258 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"9875_CR8","doi-asserted-by":"crossref","unstructured":"Lutz, J.H.: The quantitative structure of exponential time. In: Hemaspaandra, L.A., Selman, A.L. (eds.) Complexity Theory Retrospective II, pp 225\u2013254. Springer (1997)","DOI":"10.1007\/978-1-4612-1872-2_10"},{"issue":"5","key":"9875_CR9","doi-asserted-by":"publisher","first-page":"1236","DOI":"10.1137\/S0097539701417723","volume":"32","author":"JH Lutz","year":"2003","unstructured":"Lutz, J.H.: Dimension in complexity classes. SIAM J. Comput. 32(5), 1236\u20131259 (2003)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"9875_CR10","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(95)00189-1","volume":"164","author":"JH Lutz","year":"1996","unstructured":"Lutz, J.H., Mayordomo, E.: Cook versus Karp-Levin: Separating completeness notions if NP is not small. Theor. Comput. Sci. 164(1\u20132), 141\u2013163 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"9875_CR11","first-page":"64","volume":"68","author":"JH Lutz","year":"1999","unstructured":"Lutz, J.H., Mayordomo, E.: Twelve problems in resource-bounded measure. Bull. European Assoc. Theor. Comput. Sci. 68, 64\u201380 (1999). Also in Current Trends in Theoretical Computer Science: Entering the 21st Century, pages 83\u2013101 World Scientific Publishing, 2001","journal-title":"Bull. European Assoc. Theor. Comput. Sci."},{"issue":"1-3","key":"9875_CR12","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.tcs.2008.02.013","volume":"400","author":"P Moser","year":"2008","unstructured":"Moser, P.: Martingale families and dimension in P. Theor. Comput. Sci. 400 (1-3), 46\u201361 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"9875_CR13","unstructured":"O\u2019Donnell, R.: Analysis of Boolean Functions. Cambridge University Press (2014)"},{"issue":"1","key":"9875_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1997.2639","volume":"136","author":"M Strauss","year":"1997","unstructured":"Strauss, M.: Measure on P: Strength of the notion. Inf. Comput. 136(1), 1\u201323 (1997)","journal-title":"Inf. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9875-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-018-9875-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9875-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T11:26:19Z","timestamp":1751714779000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-018-9875-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,28]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["9875"],"URL":"https:\/\/doi.org\/10.1007\/s00224-018-9875-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2018,6,28]]},"assertion":[{"value":"28 June 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}