{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,12]],"date-time":"2024-01-12T11:40:28Z","timestamp":1705059628495},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1994,5,1]],"date-time":"1994-05-01T00:00:00Z","timestamp":767750400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Systems Theory"],"published-print":{"date-parts":[[1994,5]]},"DOI":"10.1007\/bf01578842","type":"journal-article","created":{"date-parts":[[2005,4,29]],"date-time":"2005-04-29T02:18:37Z","timestamp":1114741117000},"page":"201-209","source":"Crossref","is-referenced-by-count":24,"title":["An observation on probability versus randomness with applications to complexity classes"],"prefix":"10.1007","volume":"27","author":[{"given":"Ronald V.","family":"Book","sequence":"first","affiliation":[]},{"given":"Jack H.","family":"Lutz","sequence":"additional","affiliation":[]},{"given":"Klaus W.","family":"Wagner","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","first-page":"23","volume-title":"Lecture Notes in Computer Science, Vol. 223","author":"K. Ambos-Spies","year":"1986","unstructured":"K. Ambos-Spies. Randomness, relativations, and polynomial reducibilities.Proc. First Conf. on Structure in Complexity Theory, Lecture Notes in Computer Science, Vol. 223, Springer-Verlag, Berlin, 1986, pp. 23\u201334."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1145\/5925.5937","volume":"33","author":"J. Balc\u00e1zar","year":"1986","unstructured":"J. Balc\u00e1zar, R. Book, and U. Sch\u00f6ning. The polynomial-time hierarchy and sparse oracles.J. Assoc. Comput. Mach., 33:603\u2013617, 1986.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97062-7","volume-title":"Structural Complexity I","author":"J. Balc\u00e1zar","year":"1988","unstructured":"J. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3.Structural Complexity I. Springer-Verlag, Berlin, 1988."},{"key":"CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-75357-2","volume-title":"Structural Complexity II","author":"J. Balc\u00e1zar","year":"1990","unstructured":"J. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3.Structural Complexity II. Springer-Verlag, Berlin, 1990."},{"key":"CR5","first-page":"227","volume-title":"The Universal Turing Machine: A Half-Century Survey","author":"C. Bennett","year":"1988","unstructured":"C. Bennett. Logical depth and physical complexity. InThe Universal Turing Machine: A Half-Century Survey (R. Herken, ed.), Oxford University Press, Oxford, 1988, pp. 227\u2013257."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. Bennett","year":"1981","unstructured":"C. Bennett and J. Gill. Relative to a random oracleP itA \u2260 NPitA \u2260 co-NPitA with probability 1.SIAM J. Comput., 10:96\u2013113, 1981.","journal-title":"SIAM J. Comput."},{"key":"CR7","first-page":"148","volume-title":"Lecture Notes in Computer Science, Vol. 38","author":"J.-Y. Cai","year":"1987","unstructured":"J.-Y. Cai. Probability one separation of the boolean hierarchy.Proc. STACS 87, Lecture Notes in Computer Science, Vol. 38, Springer-Verlag, Berlin, 1987, pp. 148\u2013158."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/0022-0000(89)90033-0","volume":"38","author":"J.-Y. Cai","year":"1989","unstructured":"J.-Y. Cai. With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy.J. Comput. System Sci., 38:68\u201385, 1989.","journal-title":"J. Comput. System Sci."},{"key":"CR9","first-page":"191","volume":"28","author":"R. Karp","year":"1982","unstructured":"R. Karp and R. Lipton. Turing machines, that take advice.Enseign. Math. (2), 28:191\u2013209, 1982.","journal-title":"Enseign. Math. (2)"},{"key":"CR10","unstructured":"S. Kautz. Degrees of random sets. Ph.D. dissertation, Cornell University, 1991."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1145\/5925.5938","volume":"33","author":"T. Long","year":"1986","unstructured":"T. Long and A. Selman. Relativizing complexity classes with sparse oracles.J. Assoc. Comput. Mach., 33:618\u2013627, 1986.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR12","doi-asserted-by":"crossref","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. On the definition of random sequences.Inform. and Control, 9:602\u2013619, 1966.","journal-title":"Inform. and Control"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF00534110","volume":"19","author":"P. Martin-L\u00f6f","year":"1971","unstructured":"P. Martin-L\u00f6f. Complexity oscillations in infinite binary sequences.Z. Wahrsch. Verw. Gebiete, 19:225\u2013230, 1971.","journal-title":"Z. Wahrsch. Verw. Gebiete"},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Wigderson. Hardness versus randomness.Proc. 29th IEEE Symp. on Foundations of Computer Science, 1988, pp. 2\u201311.","DOI":"10.1109\/SFCS.1988.21916"},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"M. Ogiwara and A. Lozano. On one query self-reducible sets.Proc. 6th IEEE Conf. on Structure in Complexity Theory, 1991, pp. 139\u2013151.","DOI":"10.1109\/SCT.1991.160254"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1137\/0220030","volume":"20","author":"M. Ogiwara","year":"1991","unstructured":"M. Ogiwara and O. Watanabe. On polynomial bounded truth table reducibility of NP sets to sparse sets.SIAM J. Comput., 20:471\u2013183, 1991.","journal-title":"SIAM J. Comput."},{"key":"CR17","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H. Rogers","year":"1967","unstructured":"H. Rogers.Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967."},{"key":"CR18","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/0304-3975(91)90314-R","volume":"81","author":"S. Tang","year":"1991","unstructured":"S. Tang and R. Book. Polynomial-time reducibilities and \u201calmost-all\u201d oracle sets.Theoret. Comput. Sci., 81:36\u201347, 1991.","journal-title":"Theoret. Comput. Sci."}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01578842.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01578842\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01578842","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T04:23:26Z","timestamp":1586233406000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01578842"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,5]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,5]]}},"alternative-id":["BF01578842"],"URL":"https:\/\/doi.org\/10.1007\/bf01578842","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,5]]}}}