{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:10:30Z","timestamp":1725484230889},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438649"},{"type":"electronic","value":"9783540454656"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45465-9_47","type":"book-chapter","created":{"date-parts":[[2007,5,26]],"date-time":"2007-05-26T21:12:57Z","timestamp":1180213977000},"page":"549-560","source":"Crossref","is-referenced-by-count":1,"title":["Why Computational Complexity Requires Stricter Martingales"],"prefix":"10.1007","author":[{"given":"John M.","family":"Hitchcock","sequence":"first","affiliation":[]},{"given":"Jack H.","family":"Lutz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,6,25]]},"reference":[{"key":"47_CR1","unstructured":"N. Alon and J. H. Spencer. The Probabilistic Method. Wiley, 1992."},{"key":"47_CR2","series-title":"Lecture Notes in Pure and Applied Mathematics","first-page":"1","volume-title":"Complexity, Logic and Recursion Theory","author":"K. Ambos-Spies","year":"1997","unstructured":"K. Ambos-Spies and E. Mayordomo. Resource-bounded measure and randomness. In A. Sorbi, editor, Complexity, Logic and Recursion Theory, Lecture Notes in Pure and Applied Mathematics, pages 1\u201347. Marcel Dekker, New York, N.Y., 1997."},{"key":"47_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-79235-9","volume-title":"Structural Complexity I (second edition)","author":"J. L. Balc\u00e1zar","year":"1995","unstructured":"J. L. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I (second edition). Springer-Verlag, Berlin, 1995."},{"key":"47_CR4","unstructured":"K. L. Chung. A Course in Probability Theory. Academic Press, third edition, 2001."},{"key":"47_CR5","doi-asserted-by":"publisher","first-page":"455","DOI":"10.2307\/1989964","volume":"47","author":"J. L. Doob","year":"1940","unstructured":"J. L. Doob. Regularity properties of certain families of chance variables. Transactions of the American Mathematical Society, 47:455\u2013486, 1940.","journal-title":"Transactions of the American Mathematical Society"},{"key":"47_CR6","volume-title":"Stochastic Processes","author":"J. L. Doob","year":"1953","unstructured":"J. L. Doob. Stochastic Processes. Wiley, New York, N.Y., 1953."},{"key":"47_CR7","unstructured":"R. Durrett. Essentials of Stochastic Processes. Springer, 1999."},{"key":"47_CR8","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1006\/inco.1999.2794","volume":"153","author":"J. I. Lathrop","year":"1999","unstructured":"J. I. Lathrop and J. H. Lutz. Recursive computational depth. Information and Computation, 153:139\u2013172, 1999.","journal-title":"Information and Computation"},{"issue":"4","key":"47_CR9","first-page":"347","volume":"14","author":"P. L\u00e9vy","year":"1935","unstructured":"P. L\u00e9vy. Propri\u00e9t\u00e9s asymptotiques des sommes de variables ind\u00e9pendantes ou enchain\u00e9es. Journal des math\u00e9matiques pures et appliqu\u00e9es. Series 9., 14(4):347\u2013402, 1935.","journal-title":"Journal des math\u00e9matiques pures et appliqu\u00e9es. Series 9"},{"key":"47_CR10","unstructured":"P. L\u00e9vy. Th\u00e9orie de l\u2019Addition des Variables Aleatoires. Gauthier-Villars, 1937 (second edition 1954)."},{"key":"47_CR11","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J. H. Lutz","year":"1992","unstructured":"J. H. Lutz. Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences, 44:220\u2013258, 1992.","journal-title":"Journal of Computer and System Sciences"},{"key":"47_CR12","doi-asserted-by":"crossref","unstructured":"J. H. Lutz. The quantitative structure of exponential time. In L.A. Hemaspaan-dra and A.L. Selman, editors, Complexity Theory Retrospective II, pages 225\u2013254. Springer-Verlag, 1997.","DOI":"10.1007\/978-1-4612-1872-2_10"},{"key":"47_CR13","doi-asserted-by":"crossref","unstructured":"J. H. Lutz. Resource-bounded measure. In Proceedings of the 13th IEEE Conference on Computational Complexity, pages 236\u2013248, New York, 1998. IEEE Computer Society Press.","DOI":"10.1109\/CCC.1998.694611"},{"key":"47_CR14","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","volume":"9","author":"P. Martin-L\u00f6f","year":"1966","unstructured":"P. Martin-L\u00f6f. The definition of random sequences. Information and Control, 9:602\u2013619, 1966.","journal-title":"Information and Control"},{"key":"47_CR15","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"47_CR16","doi-asserted-by":"crossref","unstructured":"S. M. Ross. Stochastic Processes. Wiley, 1983.","DOI":"10.1016\/B978-0-12-598420-1.50011-8"},{"key":"47_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00538763","volume":"16","author":"C. P. Schnorr","year":"1970","unstructured":"C. P. Schnorr. Klassifikation der Zufallsgesetze nach Komplexit\u00e4t und Ordnung. Z. Wahrscheinlichkeitstheorie verw. Geb., 16:1\u201321, 1970.","journal-title":"Z. Wahrscheinlichkeitstheorie verw. Geb."},{"key":"47_CR18","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/BF01694181","volume":"5","author":"C. P. Schnorr","year":"1971","unstructured":"C. P. Schnorr. A unified approach to the definition of random sequences. Mathematical Systems Theory, 5:246\u2013258, 1971.","journal-title":"Mathematical Systems Theory"},{"key":"47_CR19","doi-asserted-by":"crossref","unstructured":"C. P. Schnorr. Zuf\u00e4lligkeit und Wahrscheinlichkeit. Lecture Notes in Mathematics, 218, 1971.","DOI":"10.1007\/BFb0112458"},{"key":"47_CR20","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1016\/S0022-0000(73)80030-3","volume":"7","author":"C. P. Schnorr","year":"1973","unstructured":"C. P. Schnorr. Process complexity and effective random tests. Journal of Computer and System Sciences, 7:376\u2013388, 1973.","journal-title":"Journal of Computer and System Sciences"},{"key":"47_CR21","volume-title":"Etude Critique de la Notion de Collectif\u2019","author":"J. Ville","year":"1939","unstructured":"J. Ville. Etude Critique de la Notion de Collectif\u2019. Gauthier-Villars, Paris, 1939."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45465-9_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T07:05:55Z","timestamp":1556435155000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45465-9_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438649","9783540454656"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-45465-9_47","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}