{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T15:32:59Z","timestamp":1747150379799,"version":"3.40.5"},"reference-count":15,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T00:00:00Z","timestamp":1722556800000},"content-version":"am","delay-in-days":367,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#am"},{"start":{"date-parts":[[2023,8,2]],"date-time":"2023-08-02T00:00:00Z","timestamp":1690934400000},"content-version":"vor","delay-in-days":1,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS 1800323"],"award-info":[{"award-number":["DMS 1800323"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We prove two sets of results concerning computational complexity classes. First, we propose a new variation of the random oracle hypothesis, originally posed by Bennett and Gill after they showed that relative to a randomly chosen oracle, with probability 1. Their original hypothesis was quickly disproven in several ways, most famously in 1992 with the result that , in spite of the classes being shown unequal with probability 1. Here we propose a variation of what it means to be \u201clarge\u201d using the Ellentuck topology. In this new context, we demonstrate that the set of oracles separating and is not small, and obtain similar results for the separation of from along with the separation of from . We also show that the set of oracles<jats:italic>equating<\/jats:italic>with is large in this new sense. We demonstrate that this version of the hypothesis provides a sufficient condition for unrelativized relationships, at least in the cases considered here. Second, we examine the descriptive complexity of the classes of oracles providing the separations for these various classes, and determine their exact placement in the Borel\u00a0hierarchy.<\/jats:p>","DOI":"10.1002\/malq.202200068","type":"journal-article","created":{"date-parts":[[2023,8,2]],"date-time":"2023-08-02T12:14:25Z","timestamp":1690978465000},"page":"267-286","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Borel complexity and Ramsey largeness of sets of oracles separating complexity classes"],"prefix":"10.1002","volume":"69","author":[{"given":"Alex","family":"Creiner","sequence":"first","affiliation":[{"name":"Department of Mathematics University of North Texas Denton United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2399-0129","authenticated-orcid":false,"given":"Stephen","family":"Jackson","sequence":"additional","affiliation":[{"name":"Department of Mathematics University of North Texas Denton United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2023,8,2]]},"reference":[{"key":"e_1_2_7_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90036-6"},{"key":"e_1_2_7_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"e_1_2_7_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300933"},{"key":"e_1_2_7_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210008"},{"key":"e_1_2_7_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300921"},{"key":"e_1_2_7_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90033-0"},{"key":"e_1_2_7_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80084-4"},{"key":"e_1_2_7_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"volume-title":"Computational Limitations of Small\u2010Depth Circuits","year":"1987","author":"H\u00e5stad J.","key":"e_1_2_7_10_1"},{"key":"e_1_2_7_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4190-4"},{"key":"e_1_2_7_12_1","unstructured":"D.KozenandM.Machtey On relative diagonals Tech. Rep. RC8184 IBM Thomas J. Watson Research Center(April1980)."},{"key":"e_1_2_7_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80023-0"},{"key":"e_1_2_7_14_1","doi-asserted-by":"crossref","unstructured":"B.Rossman R. A.Servedio andL. Y.Tan An average\u2010case depth hierarchy theorem for boolean circuits preprint arXiv:1504.03398 (2015).","DOI":"10.1109\/FOCS.2015.67"},{"key":"e_1_2_7_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_2_7_16_1","doi-asserted-by":"crossref","unstructured":"A. C.\u2010C.Yao Separating the polynomial\u2010time hierarchy by oracles in:26th Annual Symposium on Foundations of Computer Science (sfcs 1985) Portland OR USA(1985) pp.1\u201310.","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/am-pdf\/10.1002\/malq.202200068","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.202200068","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T14:59:15Z","timestamp":1729868355000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.202200068"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["10.1002\/malq.202200068"],"URL":"https:\/\/doi.org\/10.1002\/malq.202200068","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"type":"print","value":"0942-5616"},{"type":"electronic","value":"1521-3870"}],"subject":[],"published":{"date-parts":[[2023,8]]},"assertion":[{"value":"2022-12-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-25","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-08-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}