We show that if the Boolean hierarchy collapses to level k, then the polynomial hierarchy collapses to BH3(k), where BH3(k) is the kth level of the Boolean hierarchy over Sigma(2)(P). This is an improvement over the k...
详细信息
We show that if the Boolean hierarchy collapses to level k, then the polynomial hierarchy collapses to BH3(k), where BH3(k) is the kth level of the Boolean hierarchy over Sigma(2)(P). This is an improvement over the known results, which show that the polynomial hierarchy would collapse to (PO)-O-NPNP[(log n)]. This result is significant in two ways. First, the theorem says that a deeper collapse of the Boolean hierarchy implies a deeper collapse of the polynomial hierarchy. Also, this result points to some previously unexplored connections between the Boolean and query hierarchies of Delta(2)(P) and Delta(3)(P). Namely, BH(k) = co-BH(k) double right arrow BH3(k) = co-BH3(k), P(NP)parallel to[k] = P(NP)parallel to[k+1] double right arrow P-NPNP parallel to[k+1] = P-NPNP parallel to[k+2].
暂无评论