ECCC-Report TR14-050https://eccc.weizmann.ac.il/report/2014/050Comments and Revisions published for TR14-050en-usTue, 15 Apr 2014 10:49:06 +0300
Revision 1
| On the probabilistic closure of the loose unambiguous hierarchy |
Edward Hirsch,
Dmitry Sokolov
https://eccc.weizmann.ac.il/report/2014/050#revision1Unambiguous 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.Tue, 15 Apr 2014 10:49:06 +0300https://eccc.weizmann.ac.il/report/2014/050#revision1
Paper TR14-050
| On the probabilistic closure of the loose unambiguous hierarchy |
Edward Hirsch,
Dmitry Sokolov
https://eccc.weizmann.ac.il/report/2014/050Unambiguous 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.Fri, 11 Apr 2014 13:59:53 +0300https://eccc.weizmann.ac.il/report/2014/050