{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:12Z","timestamp":1750220592190,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T00:00:00Z","timestamp":1611187200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2021,3,31]]},"abstract":"<jats:p>\n            Bennett and Gill [1981] showed that P\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            \u2260 NP\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            \u2260 coNP\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            for a random oracle\n            <jats:italic>A<\/jats:italic>\n            , with probability 1. We investigate whether this result extends to individual polynomial-time random oracles. We consider two notions of random oracles: p-random oracles in the sense of martingales and resource-bounded measure [Lutz 1992; Ambos-Spies et\u00a0al. 1997], and p-betting-game random oracles using the betting games generalization of resource-bounded measure [Buhrman et\u00a0al. 2000]. Every p-betting-game random oracle is also p-random; whether the two notions are equivalent is an open problem.\n          <\/jats:p>\n          <jats:p>\n            (1) We first show that P\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            \u2260 NP\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            for every oracle\n            <jats:italic>A<\/jats:italic>\n            that is p-betting-game random.\n          <\/jats:p>\n          <jats:p>Ideally, we would extend (1) to p-random oracles. We show that answering this either way would imply an unrelativized complexity class separation:<\/jats:p>\n          <jats:p>\n            (2) If P\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            \u2260 NP\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            relative to every p-random oracle\n            <jats:italic>A<\/jats:italic>\n            , then BPP \u2260 EXP.\n          <\/jats:p>\n          <jats:p>\n            (3) If P\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            \u2260 NP\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            relative to some p-random oracle\n            <jats:italic>A<\/jats:italic>\n            , then P \u2260 PSPACE.\n          <\/jats:p>\n          <jats:p>\n            Rossman, Servedio, and Tan [2015] showed that the polynomial-time hierarchy is infinite relative to a random oracle, solving a longstanding open problem. We consider whether we can extend (1) to show that PH\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            is infinite relative to oracles\n            <jats:italic>A<\/jats:italic>\n            that are p-betting-game random. Showing that PH\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            separates at even its first level would also imply an unrelativized complexity class separation:\n          <\/jats:p>\n          <jats:p>\n            (4) If NP\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            \u2260 coNP\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            for a p-betting-game measure 1 class of oracles\n            <jats:italic>A<\/jats:italic>\n            , then NP \u2260 EXP.\n          <\/jats:p>\n          <jats:p>\n            (5) If PH\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            is infinite relative to every p-random oracle\n            <jats:italic>A<\/jats:italic>\n            , then PH \u2260 EXP.\n          <\/jats:p>\n          <jats:p>We also consider random oracles for time versus space, for example:<\/jats:p>\n          <jats:p>\n            (6) L\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            \u2260 P\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            relative to every oracle\n            <jats:italic>A<\/jats:italic>\n            that is p-betting-game random.\n          <\/jats:p>","DOI":"10.1145\/3434389","type":"journal-article","created":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T11:11:18Z","timestamp":1611227478000},"page":"11-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial-Time Random Oracles and Separating Complexity Classes"],"prefix":"10.1145","volume":"13","author":[{"given":"John M.","family":"Hitchcock","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Wyoming"}]},{"given":"Adewale","family":"Sekoni","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Computer Science 8 Physics, Roanoke College"}]},{"given":"Hadi","family":"Shafei","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Northern Michigan University"}]}],"member":"320","published-online":{"date-parts":[[2021,1,21]]},"reference":[{"volume-title":"Proceedings of the 35th Symposium on Foundations of Computer Science. IEEE Computer Society, 807--818","author":"Allender E.","key":"e_1_2_1_1_1","unstructured":"E. Allender and M. Strauss . 1994. Measure on small complexity classes with applications for BPP . In Proceedings of the 35th Symposium on Foundations of Computer Science. IEEE Computer Society, 807--818 E. Allender and M. Strauss. 1994. Measure on small complexity classes with applications for BPP. In Proceedings of the 35th Symposium on Foundations of Computer Science. IEEE Computer Society, 807--818"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies and E. Mayordomo. 1997. Resource-bounded measure and randomness. In Complexity Logic and Recursion Theory A. Sorbi (Ed.). Marcel Dekker New York NY 1--47.  K. Ambos-Spies and E. Mayordomo. 1997. Resource-bounded measure and randomness. In Complexity Logic and Recursion Theory A. Sorbi (Ed.). Marcel Dekker New York NY 1--47.","DOI":"10.1201\/9780429187490-1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90036-6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1989.41827"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210008"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(74)90473-2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01578842"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"576","DOI":"10.1137\/S0097539798343891","article-title":"A generalization of resource-bounded measure, with application to the BPP vs. EXP problem","volume":"30","author":"Buhrman H.","year":"2001","unstructured":"H. Buhrman , D. van Melkebeek , K. W. Regan , D. Sivakumar , and M. Strauss . 2001 . A generalization of resource-bounded measure, with application to the BPP vs. EXP problem . SIAM Journal on Computing 30 , 2 (2001), 576 -- 601 . http:\/\/pages.cs.wisc.edu\/ dieter\/Research\/m-betting.html. H. Buhrman, D. van Melkebeek, K. W. Regan, D. Sivakumar, and M. Strauss. 2001. A generalization of resource-bounded measure, with application to the BPP vs. EXP problem. SIAM Journal on Computing 30, 2 (2001), 576--601. http:\/\/pages.cs.wisc.edu\/ dieter\/Research\/m-betting.html.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90033-0"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80084-4"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2539126.2539130"},{"volume-title":"Computational Limitations for Small-Depth Circuits","author":"H\u00e5stad J.","key":"e_1_2_1_12_1","unstructured":"J. H\u00e5stad . 1986. Computational Limitations for Small-Depth Circuits . The MIT Press . J. H\u00e5stad. 1986. Computational Limitations for Small-Depth Circuits. The MIT Press."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.01.025"},{"key":"e_1_2_1_14_1","first-page":"3","article-title":"The fractal geometry of complexity classes","volume":"36","author":"Hitchcock J. M.","year":"2005","unstructured":"J. M. Hitchcock , J. H. Lutz , and E. Mayordomo . 2005 . The fractal geometry of complexity classes . SIGACT News 36 , 3 (September 2005), 24--38. http:\/\/www.cs.uwyo.edu\/ jhitchco\/papers\/fgcc.shtml. J. M. Hitchcock, J. H. Lutz, and E. Mayordomo. 2005. The fractal geometry of complexity classes. SIGACT News 36, 3 (September 2005), 24--38. http:\/\/www.cs.uwyo.edu\/ jhitchco\/papers\/fgcc.shtml.","journal-title":"SIGACT News"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0304-3975(95)80030-D","article-title":"Weak completeness in E and E2","volume":"143","author":"Juedes D. W.","year":"1995","unstructured":"D. W. Juedes and J. H. Lutz . 1995 . Weak completeness in E and E2 . Theoretical Computer Science 143 , 1 (1995), 149 -- 158 . D. W. Juedes and J. H. Lutz. 1995. Weak completeness in E and E2. Theoretical Computer Science 143, 1 (1995), 149--158.","journal-title":"Theoretical Computer Science"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90020-J"},{"volume-title":"The quantitative structure of exponential time","author":"Lutz J. H.","key":"e_1_2_1_17_1","unstructured":"J. H. Lutz . 1997. The quantitative structure of exponential time . In Complexity Theory Retrospective II, L. A. Hemaspaandra and A. L. Selman (Eds.). Springer-Verlag , 225--254. J. H. Lutz. 1997. The quantitative structure of exponential time. In Complexity Theory Retrospective II, L. A. Hemaspaandra and A. L. Selman (Eds.). Springer-Verlag, 225--254."},{"key":"e_1_2_1_18_1","first-page":"1","article-title":"Circuit size relative to pseudorandom oracles","volume":"107","author":"Lutz J. H.","year":"1993","unstructured":"J. H. Lutz and W. J. Schmidt . 1993 . Circuit size relative to pseudorandom oracles . Theoretical Computer Science 107 , 1 (March 1993), 95--120. J. H. Lutz and W. J. Schmidt. 1993. Circuit size relative to pseudorandom oracles. Theoretical Computer Science 107, 1 (March 1993), 95--120.","journal-title":"Theoretical Computer Science"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80018-9"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2005.06.011"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00069-3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 56th Symposium on Foundations of Computer Science. IEEE Computer Society, 1030--1048","author":"Rossman B.","year":"2015","unstructured":"B. Rossman , R. A. Servedio , and L.-Y. Tan . 2015 . An average-case depth hierarchy theorem for Boolean circuits . In Proceedings of the 56th Symposium on Foundations of Computer Science. IEEE Computer Society, 1030--1048 . B. Rossman, R. A. Servedio, and L.-Y. Tan. 2015. An average-case depth hierarchy theorem for Boolean circuits. In Proceedings of the 56th Symposium on Foundations of Computer Science. IEEE Computer Society, 1030--1048."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434389","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434389","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:47Z","timestamp":1750195907000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434389"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,21]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,3,31]]}},"alternative-id":["10.1145\/3434389"],"URL":"https:\/\/doi.org\/10.1145\/3434389","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2021,1,21]]},"assertion":[{"value":"2019-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}