Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 3643
Articles: 2'488'730
Articles rated: 2609

29 March 2024
 
  » arxiv » cs.CC/0106037

 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
AbstractThe 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   
 
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
important:
of broad interest:
readable:
new:
correct:
Global appreciation:

  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






ScienXe.org
» my Online CV
» Free


News, job offers and information for researchers and scientists:
home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2024 - Scimetrica