Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR14-050 | 15th April 2014 10:49

On the probabilistic closure of the loose unambiguous hierarchy

RSS-Feed




Revision #1
Authors: Edward Hirsch, Dmitry Sokolov
Accepted on: 15th April 2014 10:49
Downloads: 1329
Keywords: 


Abstract:

Unambiguous hierarchies [NR93,LR94,NR98] are defined similarly to the polynomial hierarchy; however, all witnesses must be unique. These hierarchies have subtle differences in the mode of using oracles. We consider a "loose" unambiguous hierarchy $prUH_\bullet$ with relaxed definition of oracle access to promise problems. Namely, we allow to make queries that miss the promise set; however, the oracle answer in this case can be arbitrary (a similar definition of oracle access has been used in [CR08]).

We prove that the first part of Toda's theorem $PH\subseteq BP \cdot\oplus P\subseteq P^{PP}$ can be rectified to $PH=BP\cdot prUH_\bullet$, that is, the closure of our hierarchy under Schoening's $BP$ operator equals the polynomial hierarchy. It is easily seen that $BP\cdot prUH_\bullet\subseteq BP\cdot \oplus P$.

The proof follows the same lines as Toda's proof, so the main contribution of the present note is a new definition.



Changes to previous version:

Several minor corrections including Corollary 1 (a collapse of the unambiguous hierarchy implies a collapse of PH; however, the inverse result has a more intricate formulation).


Paper:

TR14-050 | 21st March 2014 17:30

On the probabilistic closure of the loose unambiguous hierarchy





TR14-050
Authors: Edward Hirsch, Dmitry Sokolov
Publication: 11th April 2014 13:59
Downloads: 805
Keywords: 


Abstract:

Unambiguous hierarchies [NR93,LR94,NR98] are defined similarly to the polynomial hierarchy; however, all witnesses must be unique. These hierarchies have subtle differences in the mode of using oracles. We consider a "loose" unambiguous hierarchy $prUH_\bullet$ with relaxed definition of oracle access to promise problems. Namely, we allow to make queries that miss the promise set; however, the oracle answer in this case can be arbitrary (a similar definition of oracle access has been used in [CR08]).

We prove that the first part of Toda's theorem $PH\subseteq BP \cdot\oplus P\subseteq P^{PP}$ can be rectified to $PH=BP\cdot prUH_\bullet$, that is, the closure of our hierarchy under Schoening's $BP$ operator equals the polynomial hierarchy. It is easily seen that $BP\cdot prUH_\bullet\subseteq BP\cdot \oplus P$.

The proof follows the same lines as Toda's proof, so the main contribution of the present note is a new definition.



ISSN 1433-8092 | Imprint