| | |
| | |
Stat |
Members: 3643 Articles: 2'488'730 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
Using the No-Search Easy-Hard Technique for Downward Collapse | Edith Hemaspaandra
; Lane A. Hemaspaandra
; Harald Hempel
; | Date: |
15 Jun 2001 | Subject: | Computational Complexity ACM-class: F.1.3; F.1.2 | cs.CC | Abstract: | The top part of the preceding figure [figure appears in actual paper] shows some classes from the (truth-table) bounded-query and boolean hierarchies. It is well-known that if either of these hierarchies collapses at a given level, then all higher levels of that hierarchy collapse to that same level. This is a standard ``upward translation of equality’’ that has been known for over a decade. The issue of whether these hierarchies can translate equality {em downwards/} has proven vastly more challenging. In particular, with regard to the figure above, consider the following claim: $$P_{m-tt}^{Sigma_k^p} = P_{m+1-tt}^{Sigma_k^p} implies DIFF_m(Sigma_k^p) coDIFF_m(Sigma_k^p) = BH(Sigma_k^p). (*) $$ This claim, if true, says that equality translates downwards between levels of the bounded-query hierarchy and the boolean hierarchy levels that (before the fact) are immediately below them. Until recently, it was not known whether (*) {em ever/} held, except for the degenerate cases $m=0$ and $k=0$. Then Hemaspaandra, Hemaspaandra, and Hempel cite{hem-hem-hem:j:downward-translation} proved that (*) holds for all $m$, for $k > 2$. Buhrman and Fortnow~cite{buh-for:j:two-queries} then showed that, when $k=2$, (*) holds for the case $m = 1$. In this paper, we prove that for the case $k=2$, (*) holds for all values of $m$. Since there is an oracle relative to which ``for $k=1$, (*) holds for all $m$’’ fails cite{buh-for:j:two-queries}, our achievement of the $k=2$ case cannot to be strengthened to $k=1$ by any relativizable proof technique. The new downward translation we obtain also tightens the collapse in the polynomial hierarchy implied by a collapse in the bounded-query hierarchy of the second level of the polynomial hierarchy. | Source: | arXiv, cs.CC/0106037 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |