Standard

On the probabilistic closure of the loose unambiguous hierarchy. / Hirsch, Edward A.; Sokolov, Dmitry.

In: Information Processing Letters, Vol. 115, No. 9, 01.09.2015, p. 725-730.

Research output: Contribution to journal › Article › peer-review

Harvard

Hirsch, EA & Sokolov, D 2015, 'On the probabilistic closure of the loose unambiguous hierarchy', Information Processing Letters, vol. 115, no. 9, pp. 725-730. https://doi.org/10.1016/j.ipl.2015.04.010

APA

Hirsch, E. A., & Sokolov, D. (2015). On the probabilistic closure of the loose unambiguous hierarchy. Information Processing Letters, 115(9), 725-730. https://doi.org/10.1016/j.ipl.2015.04.010

Vancouver

Hirsch EA, Sokolov D. On the probabilistic closure of the loose unambiguous hierarchy. Information Processing Letters. 2015 Sep 1;115(9):725-730. https://doi.org/10.1016/j.ipl.2015.04.010

Author

Hirsch, Edward A. ; Sokolov, Dmitry. / On the probabilistic closure of the loose unambiguous hierarchy. In: Information Processing Letters. 2015 ; Vol. 115, No. 9. pp. 725-730.

BibTeX

@article{245a7c0eceb84c1b9eb4816c110cf8a6,
title = "On the probabilistic closure of the loose unambiguous hierarchy",
abstract = "Unambiguous hierarchies [1-3] 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• 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 [4]). In this short note we prove that the first part of Toda's theorem PH⊂BP.⊕P⊂PPP can be strengthened to PH=BP.prUH•, that is, the closure of our hierarchy under Sch{\"o}ning's BP operator equals the polynomial hierarchy. It is easily seen that BP.prUH•⊂BP.⊕P. The proof follows the same lines as Toda's proof, so the main contribution of the present note is a new definition that allows to characterize PH as a probabilistic closure of unambiguous computations.",
keywords = "Computational complexity, Randomized algorithms, Toda's theorem, Unambiguous computations",
author = "Hirsch, {Edward A.} and Dmitry Sokolov",
year = "2015",
month = sep,
day = "1",
doi = "10.1016/j.ipl.2015.04.010",
language = "English",
volume = "115",
pages = "725--730",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "9",

}

RIS

TY - JOUR

T1 - On the probabilistic closure of the loose unambiguous hierarchy

AU - Hirsch, Edward A.

AU - Sokolov, Dmitry

PY - 2015/9/1

Y1 - 2015/9/1

N2 - Unambiguous hierarchies [1-3] 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• 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 [4]). In this short note we prove that the first part of Toda's theorem PH⊂BP.⊕P⊂PPP can be strengthened to PH=BP.prUH•, that is, the closure of our hierarchy under Schöning's BP operator equals the polynomial hierarchy. It is easily seen that BP.prUH•⊂BP.⊕P. The proof follows the same lines as Toda's proof, so the main contribution of the present note is a new definition that allows to characterize PH as a probabilistic closure of unambiguous computations.

AB - Unambiguous hierarchies [1-3] 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• 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 [4]). In this short note we prove that the first part of Toda's theorem PH⊂BP.⊕P⊂PPP can be strengthened to PH=BP.prUH•, that is, the closure of our hierarchy under Schöning's BP operator equals the polynomial hierarchy. It is easily seen that BP.prUH•⊂BP.⊕P. The proof follows the same lines as Toda's proof, so the main contribution of the present note is a new definition that allows to characterize PH as a probabilistic closure of unambiguous computations.

KW - Computational complexity

KW - Randomized algorithms

KW - Toda's theorem

KW - Unambiguous computations

UR - http://www.scopus.com/inward/record.url?scp=84929956067&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2015.04.010

DO - 10.1016/j.ipl.2015.04.010

M3 - Article

AN - SCOPUS:84929956067

VL - 115

SP - 725

EP - 730

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 9

ER -

ID: 49827548