The Experts below are selected from a list of 306 Experts worldwide ranked by ideXlab platform
Harald Hempel - One of the best experts on this subject based on the ideXlab platform.
-
the operators min and max on the Polynomial Hierarchy
International Journal of Foundations of Computer Science, 2000Co-Authors: Harald Hempel, Gerd WechsungAbstract:By defining a general max and a general min operator for complexity classes we obtain that there are other interesting classes of optimization functions besides Krentel's class OptP. We investigate the behavior of these operators on the Polynomial Hierarchy, in particular we study the inclusion structure of the classes max · P, max · NP, max · coNP, min · P, min · NP, and min · coNP. It turns out that our operators when applied to the Polynomial Hierarchy yield a refinement of Krentel's Hierarchy of optimization functions. We prove that this refinement is strict unless the Polynomial Hierarchy collapses and show that the refinement is useful to exactly classify optimization functions. Moreover, our investigations shed new light on Krentel's result that every function from some level of the Polynomial Hierarchy can be characterized in terms of an optimization function.
-
Query Order and the Polynomial Hierarchy
arXiv: Computational Complexity, 1999Co-Authors: Edith Hemaspaandra, Lane A Hemaspaandra, Harald HempelAbstract:Hemaspaandra, Hempel, and Wechsung [cs.CC/9909020] initiated the field of query order, which studies the ways in which computational power is affected by the order in which information sources are accessed. The present paper studies, for the first time, query order as it applies to the levels of the Polynomial Hierarchy. We prove that the levels of the Polynomial Hierarchy are order-oblivious. Yet, we also show that these ordered query classes form new levels in the Polynomial Hierarchy unless the Polynomial Hierarchy collapses. We prove that all leaf language classes - and thus essentially all standard complexity classes - inherit all order-obliviousness results that hold for P.
-
a downward collapse within the Polynomial Hierarchy
arXiv: Computational Complexity, 1999Co-Authors: Edith Hemaspaandra, Lane A Hemaspaandra, Harald HempelAbstract:Downward collapse (a.k.a. upward separation) refers to cases where the equality of two larger classes implies the equality of two smaller classes. We provide an unqualified downward collapse result completely within the Polynomial Hierarchy. In particular, we prove that, for k > 2, if $\psigkone = \psigktwo$ then $\sigmak = \pik = \ph$. We extend this to obtain a more general downward collapse result.
-
An Introduction to Query Order
arXiv: Computational Complexity, 1999Co-Authors: Edith Hemaspaandra, Lane A Hemaspaandra, Harald HempelAbstract:Hemaspaandra, Hempel, and Wechsung [cs.CC/9909020] raised the following questions: If one is allowed one question to each of two different information sources, does the order in which one asks the questions affect the class of problems that one can solve with the given access? If so, which order yields the greater computational power? The answers to these questions have been learned-inasfar as they can be learned without resolving whether or not the Polynomial Hierarchy collapses-for both the Polynomial Hierarchy and the boolean Hierarchy. In the Polynomial Hierarchy, query order never matters. In the boolean Hierarchy, query order sometimes does not matter and, unless the Polynomial Hierarchy collapses, sometimes does matter. Furthermore, the study of query order has yielded dividends in seemingly unrelated areas, such as bottleneck computations and downward translation of equality. In this article, we present some of the central results on query order. The article is written in such a way as to encourage the reader to try his or her own hand at proving some of these results. We also give literature pointers to the quickly growing set of related results and applications.
-
a downward collapse within the Polynomial Hierarchy
SIAM Journal on Computing, 1999Co-Authors: Edith Hemaspaandra, Lane A Hemaspaandra, Harald HempelAbstract:Downward collapse (also known as upward separation) refers to cases where the equality of two larger classes implies the equality of two smaller classes. We provide an unqualified downward collapse result completely within the Polynomial Hierarchy. In particular, we prove that, for k > 2, if ${\rm P}^{\Sigma^p_k[1]} = {\rm P}^{\Sigma^p_k[2]}$ then $\Sigma^p_k = \Pi^p_k = {\rm PH}$. We extend this to obtain a more general downward collapse result.
Jun Tarui - One of the best experts on this subject based on the ideXlab platform.
-
randomized Polynomials threshold circuits and the Polynomial Hierarchy
Symposium on Theoretical Aspects of Computer Science, 1991Co-Authors: Jun TaruiAbstract:A randomized Polynomial over the integers is a multivariate Polynomial whose coefficients are integer-valued random variables. A randomized Polynomial uses m random bits if its coefficients jointly depend on m independently and uniformly distributed random bits. We show that every Boolean function family in AC0 can be computed with small error by randomized Polynomials over the integers that have degree (log n)O(1) and use (log n)O(1) random bits. Applying this result, we further show the following: (a) Every Boolean function family in AC0 is computable by depth-two probabilistic threshold circuits of size \(n^{(\log n)^{O(1)} }\) with one-sided error and is also computable by depth-three deterministic threshold circuits with linear number of threshold gates and \(n^{(\log n)^{O(1)} }\)AND gates. (b) Every language in the Polynomial Hierarchy is reducible to some language in the class PP (in fact, to some language in the class C=P) by a randomized Polynomial-time reduction with one-sided error.
-
STACS - Randomized Polynomials, threshold circuits, and the Polynomial Hierarchy
STACS 91, 1991Co-Authors: Jun TaruiAbstract:A randomized Polynomial over the integers is a multivariate Polynomial whose coefficients are integer-valued random variables. A randomized Polynomial uses m random bits if its coefficients jointly depend on m independently and uniformly distributed random bits. We show that every Boolean function family in AC0 can be computed with small error by randomized Polynomials over the integers that have degree (log n)O(1) and use (log n)O(1) random bits. Applying this result, we further show the following: (a) Every Boolean function family in AC0 is computable by depth-two probabilistic threshold circuits of size \(n^{(\log n)^{O(1)} }\) with one-sided error and is also computable by depth-three deterministic threshold circuits with linear number of threshold gates and \(n^{(\log n)^{O(1)} }\)AND gates. (b) Every language in the Polynomial Hierarchy is reducible to some language in the class PP (in fact, to some language in the class C=P) by a randomized Polynomial-time reduction with one-sided error.
Lane A Hemaspaandra - One of the best experts on this subject based on the ideXlab platform.
-
Query Order and the Polynomial Hierarchy
arXiv: Computational Complexity, 1999Co-Authors: Edith Hemaspaandra, Lane A Hemaspaandra, Harald HempelAbstract:Hemaspaandra, Hempel, and Wechsung [cs.CC/9909020] initiated the field of query order, which studies the ways in which computational power is affected by the order in which information sources are accessed. The present paper studies, for the first time, query order as it applies to the levels of the Polynomial Hierarchy. We prove that the levels of the Polynomial Hierarchy are order-oblivious. Yet, we also show that these ordered query classes form new levels in the Polynomial Hierarchy unless the Polynomial Hierarchy collapses. We prove that all leaf language classes - and thus essentially all standard complexity classes - inherit all order-obliviousness results that hold for P.
-
a downward collapse within the Polynomial Hierarchy
arXiv: Computational Complexity, 1999Co-Authors: Edith Hemaspaandra, Lane A Hemaspaandra, Harald HempelAbstract:Downward collapse (a.k.a. upward separation) refers to cases where the equality of two larger classes implies the equality of two smaller classes. We provide an unqualified downward collapse result completely within the Polynomial Hierarchy. In particular, we prove that, for k > 2, if $\psigkone = \psigktwo$ then $\sigmak = \pik = \ph$. We extend this to obtain a more general downward collapse result.
-
An Introduction to Query Order
arXiv: Computational Complexity, 1999Co-Authors: Edith Hemaspaandra, Lane A Hemaspaandra, Harald HempelAbstract:Hemaspaandra, Hempel, and Wechsung [cs.CC/9909020] raised the following questions: If one is allowed one question to each of two different information sources, does the order in which one asks the questions affect the class of problems that one can solve with the given access? If so, which order yields the greater computational power? The answers to these questions have been learned-inasfar as they can be learned without resolving whether or not the Polynomial Hierarchy collapses-for both the Polynomial Hierarchy and the boolean Hierarchy. In the Polynomial Hierarchy, query order never matters. In the boolean Hierarchy, query order sometimes does not matter and, unless the Polynomial Hierarchy collapses, sometimes does matter. Furthermore, the study of query order has yielded dividends in seemingly unrelated areas, such as bottleneck computations and downward translation of equality. In this article, we present some of the central results on query order. The article is written in such a way as to encourage the reader to try his or her own hand at proving some of these results. We also give literature pointers to the quickly growing set of related results and applications.
-
Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
arXiv: Computational Complexity, 1999Co-Authors: Lane A Hemaspaandra, Jorg RotheAbstract:It is known that for any class C closed under union and intersection, the Boolean closure of C, the Boolean Hierarchy over C, and the symmetric difference Hierarchy over C all are equal. We prove that these equalities hold for any complexity class closed under intersection; in particular, they thus hold for unambiguous Polynomial time (UP). In contrast to the NP case, we prove that the Hausdorff Hierarchy and the nested difference Hierarchy over UP both fail to capture the Boolean closure of UP in some relativized worlds. Karp and Lipton proved that if nondeterministic Polynomial time has sparse Turing-complete sets, then the Polynomial Hierarchy collapses. We establish the first consequences from the assumption that unambiguous Polynomial time has sparse Turing-complete sets: (a) UP is in Low_2, where Low_2 is the second level of the low Hierarchy, and (b) each level of the unambiguous Polynomial Hierarchy is contained one level lower in the promise unambiguous Polynomial Hierarchy than is otherwise known to be the case.
-
a downward collapse within the Polynomial Hierarchy
SIAM Journal on Computing, 1999Co-Authors: Edith Hemaspaandra, Lane A Hemaspaandra, Harald HempelAbstract:Downward collapse (also known as upward separation) refers to cases where the equality of two larger classes implies the equality of two smaller classes. We provide an unqualified downward collapse result completely within the Polynomial Hierarchy. In particular, we prove that, for k > 2, if ${\rm P}^{\Sigma^p_k[1]} = {\rm P}^{\Sigma^p_k[2]}$ then $\Sigma^p_k = \Pi^p_k = {\rm PH}$. We extend this to obtain a more general downward collapse result.
Edith Hemaspaandra - One of the best experts on this subject based on the ideXlab platform.
-
Query Order and the Polynomial Hierarchy
arXiv: Computational Complexity, 1999Co-Authors: Edith Hemaspaandra, Lane A Hemaspaandra, Harald HempelAbstract:Hemaspaandra, Hempel, and Wechsung [cs.CC/9909020] initiated the field of query order, which studies the ways in which computational power is affected by the order in which information sources are accessed. The present paper studies, for the first time, query order as it applies to the levels of the Polynomial Hierarchy. We prove that the levels of the Polynomial Hierarchy are order-oblivious. Yet, we also show that these ordered query classes form new levels in the Polynomial Hierarchy unless the Polynomial Hierarchy collapses. We prove that all leaf language classes - and thus essentially all standard complexity classes - inherit all order-obliviousness results that hold for P.
-
a downward collapse within the Polynomial Hierarchy
arXiv: Computational Complexity, 1999Co-Authors: Edith Hemaspaandra, Lane A Hemaspaandra, Harald HempelAbstract:Downward collapse (a.k.a. upward separation) refers to cases where the equality of two larger classes implies the equality of two smaller classes. We provide an unqualified downward collapse result completely within the Polynomial Hierarchy. In particular, we prove that, for k > 2, if $\psigkone = \psigktwo$ then $\sigmak = \pik = \ph$. We extend this to obtain a more general downward collapse result.
-
An Introduction to Query Order
arXiv: Computational Complexity, 1999Co-Authors: Edith Hemaspaandra, Lane A Hemaspaandra, Harald HempelAbstract:Hemaspaandra, Hempel, and Wechsung [cs.CC/9909020] raised the following questions: If one is allowed one question to each of two different information sources, does the order in which one asks the questions affect the class of problems that one can solve with the given access? If so, which order yields the greater computational power? The answers to these questions have been learned-inasfar as they can be learned without resolving whether or not the Polynomial Hierarchy collapses-for both the Polynomial Hierarchy and the boolean Hierarchy. In the Polynomial Hierarchy, query order never matters. In the boolean Hierarchy, query order sometimes does not matter and, unless the Polynomial Hierarchy collapses, sometimes does matter. Furthermore, the study of query order has yielded dividends in seemingly unrelated areas, such as bottleneck computations and downward translation of equality. In this article, we present some of the central results on query order. The article is written in such a way as to encourage the reader to try his or her own hand at proving some of these results. We also give literature pointers to the quickly growing set of related results and applications.
-
a downward collapse within the Polynomial Hierarchy
SIAM Journal on Computing, 1999Co-Authors: Edith Hemaspaandra, Lane A Hemaspaandra, Harald HempelAbstract:Downward collapse (also known as upward separation) refers to cases where the equality of two larger classes implies the equality of two smaller classes. We provide an unqualified downward collapse result completely within the Polynomial Hierarchy. In particular, we prove that, for k > 2, if ${\rm P}^{\Sigma^p_k[1]} = {\rm P}^{\Sigma^p_k[2]}$ then $\Sigma^p_k = \Pi^p_k = {\rm PH}$. We extend this to obtain a more general downward collapse result.
-
what s up with downward collapse using the easy hard technique to link boolean and Polynomial Hierarchy collapses
Sigact News, 1998Co-Authors: Edith Hemaspaandra, Lane A Hemaspaandra, Harald HempelAbstract:During the past decade, nine papers have obtained increasingly strong consequences from the assumption that boolean or bounded-query hierarchies collapse. The final four papers of this nine-paper progression actually achieve downward collapse---that is, they show that high-level collapses induce collapses at (what before-the-fact seemed to be) lower complexity levels. For example, for each k g 2 it. is now known that if one query to sp k is as powerful as two queries to sp k (i.e., PS[1] = PS[2]), then PH = sp k . This article surveys the history, the results, and the method---the so-called easy-hard technique---of the just-mentioned nine-paper progression:1. J. Kadin. The Polynomial time Hierarchy collapses if the boolean Hierarchy collapses. SIAM Journal on Computing, 17(6):1263--1282, 1988. Erratum appears in the same journal. 20(2):404.2. K. Wagner. Number-of-query hierarchies. Technical Report 158, Institut fur Mathematik. Universitat Augsburg, Augsburg, Germany, October 1987.3. K. Wagner. Number-of-query hierarchies. Technical Report 4. Institut fur Informatik. Universitat Wurzburg, Wurzburg, Germany, February 1989.4. R. Chang and J. Kadin. The boolean Hierarchy and the Polynomial Hierarchy: A closer connection. SIAM Journal on Computing. 25(2):340--354. 1996.5. R. Beigel. R. Chang. and M. Ogiwara. A relationship between difference hierarchies and relativized Polynomial hierarchies. Mathematical Systems Theory. 26(3):293--310, 1993.6. E. Hemaspaandra, L. Hemaspaandra. and H. Hempel. An upward separation in the Polynomial Hierarchy. Technical Report Math/Inf/96/15, Institut fur Informatik, Friedrich-Schiller-Universitat Jena, Jena, Germany, June 1996.7. E. Hemaspaandra, L. Hemaspaandra, and H. Hempel. A downward collapse within the Polynomial Hierarchy. SIAM Journal on Computing, 28(2):383--393, 1999.8. H. Buhrman and L. Fortnow. Two queries. In Proceedings of the 13th Annual IEEE Conference on Computational Complexity. 13--19. IEEE Computer Society Press, June 1998.9. E. Hemaspaandra, L. Hemaspaandra, and H. Hempel. Translating equality downwards. Technical Report TR-657. Department of Computer Science, University of Rochester, Rochester, NY. April 1997.
Hubie Chen - One of the best experts on this subject based on the ideXlab platform.
-
ICALP - Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness
2020Co-Authors: Hubie ChenAbstract:We present and study a framework in which one can present alternation-based lower bounds on proof length in proof systems for quantified Boolean formulas. A key notion in this framework is that of proof system ensemble, which is (essentially) a sequence of proof systems where, for each, proof checking can be performed in the Polynomial Hierarchy. We introduce a proof system ensemble called relaxing QU-res which is based on the established proof system QU-resolution. Our main results include an exponential separation of the tree-like and general versions of relaxing QU-res, and an exponential lower bound for relaxing QU-res; these are analogs of classical results in propositional proof complexity.
-
proof complexity modulo the Polynomial Hierarchy understanding alternation as a source of hardness
ACM Transactions on Computation Theory, 2017Co-Authors: Hubie ChenAbstract:We present and study a framework in which one can present alternation-based lower bounds on proof length in proof systems for quantified Boolean formulas. A key notion in this framework is that of proof system ensemble, which is (essentially) a sequence of proof systems where, for each, proof checking can be performed in the Polynomial Hierarchy. We introduce a proof system ensemble called relaxing QU-res that is based on the established proof system QU-resolution. Our main results include an exponential separation of the treelike and general versions of relaxing QU-res and an exponential lower bound for relaxing QU-res; these are analogs of classical results in propositional proof complexity.