{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:23Z","timestamp":1787337503798,"version":"build-2736575974"},"reference-count":17,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    The $\\beta$ hierarchy consists of classes $\\beta_k={\\rm NP}[log\n                    <jats:sup>kn<\/jats:sup>\n                    ]\\subseteq {\\rm NP}$. Unlike collapses in the polynomial hierarchy and the Boolean hierarchy, collapses in the $\\beta$ hierarchy do not seem to translate up, nor does closure under complement seem to cause the hierarchy to collapse. For any consistent set of collapses and separations of levels of the hierarchy that respects ${\\rm P} = \\beta_1\\subseteq \\beta_2\\subseteq \\cdots \\subseteq {\\rm NP}$, we can construct an oracle relative to which those collapses and separations hold; at the same time we can make distinct levels of the hierarchy closed under computation or not, as we wish. To give two relatively tame examples: for any $k \\geq 1$, we construct an oracle relative to which \\[ {\\rm P} = \\beta_{k} \\neq \\beta_{k+1} \\neq \\beta_{k+2} \\neq \\cdots \\] and another oracle relative to which \\[ {\\rm P} = \\beta_{k} \\neq \\beta_{k+1} = {\\rm PSPACE}. \\] We also construct an oracle relative to which $\\beta_{2k} = \\beta_{2k+1} \\neq \\beta_{2k+2}$ for all k.\n                  <\/jats:p>","DOI":"10.1137\/s0097539794277421","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1420-1429","source":"Crossref","is-referenced-by-count":1,"title":["Downward Separation Fails Catastrophically for Limited Nondeterminism Classes"],"prefix":"10.1137","volume":"27","author":[{"given":"R.","family":"Beigel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J.","family":"Goldsmith","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Carme \u00c0lvarez, Josep D\u00edaz, Jacobo Tor\u00e1n, Complexity classes with complete problems between P and NP\u2010C, Lecture Notes in Comput. Sci., Vol. 380, Springer, New York, 1989, 13\u20132491b:68032","DOI":"10.1007\/3-540-51498-8_2"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0222038"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0217078"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02090764"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"J. Goldsmith, M. Levy, and M. Mundhenk,\n                      Limited nondeterminism\n                      , SIGACT News, June 1996, pp. 20\u201329.","DOI":"10.1145\/235767.235769"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1119"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Chandra Kintala, Patrick Fischer, Computations with a restricted number of nondeterministic steps (extended abstract), Assoc. Comput. Mach., New York, 1977, 178\u201318557:18251","DOI":"10.1145\/800105.803407"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Chandra Kintala, Patrick Fischer, Computations with a restricted number of nondeterministic steps (extended abstract), Assoc. Comput. Mach., New York, 1977, 178\u201318557:18251","DOI":"10.1145\/800105.803407"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0209003"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/0218027"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0214008"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Christos Papadimitriou, Mihalis Yannakakis, On limited nondeterminism and the complexity of the V\u2010C dimension, IEEE Comput. Soc. Press, Los Alamitos, CA, 1993, 12\u20131895k:68059","DOI":"10.1109\/SCT.1993.336545"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0204018"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054194000116"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794277421","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:19Z","timestamp":1787336059000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794277421"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":17,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794277421"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794277421","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}