TY - GEN
T1 - Downward separation fails catastrophically for limited nondeterminism classes
AU - Beigel, R.
AU - Goldsmith, J.
PY - 1994
Y1 - 1994
N2 - The β hierarchy consists of sets βk = NP[logk n] NP. Unlike collapses in the polynomial hierarchy and the Boolean hierarchy, collapses in the β 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 P = β1 β2 ··· NP, we can construct an oracle relative to which those collapses and separations hold, yet any (or all) of the βk's are closed under complement. To give a few relatively tame examples: For any k≥1, we construct an oracle relative to which.
AB - The β hierarchy consists of sets βk = NP[logk n] NP. Unlike collapses in the polynomial hierarchy and the Boolean hierarchy, collapses in the β 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 P = β1 β2 ··· NP, we can construct an oracle relative to which those collapses and separations hold, yet any (or all) of the βk's are closed under complement. To give a few relatively tame examples: For any k≥1, we construct an oracle relative to which.
UR - http://www.scopus.com/inward/record.url?scp=0028590463&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0028590463&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0028590463
SN - 0818656727
T3 - Proceedings of the IEEE Annual Structure in Complexity Theory Conference
SP - 134
EP - 138
BT - Proceedings of the IEEE Annual Structure in Complexity Theory Conference
A2 - Anon, null
T2 - Proceedings of the 9th Annual Structure in Complexity Theory Conference
Y2 - 28 June 1994 through 1 July 1994
ER -