z-logo
open-access-imgOpen Access
A relationship between difference hierarchies and relativized polynomial hierarchies
Author(s) -
Richard Beigel,
Richard Chang,
Mitsunori Ogiwara
Publication year - 1993
Publication title -
mathematical systems theory
Language(s) - English
Resource type - Journals
ISSN - 0025-5661
DOI - 10.1007/bf01371729
Subject(s) - hierarchy , mathematics , combinatorics , polynomial hierarchy , class (philosophy) , bounded function , time complexity , set (abstract data type) , complexity class , p versus np problem , discrete mathematics , polynomial , computer science , mathematical analysis , artificial intelligence , economics , market economy , programming language
Chang and Kadin have shown that if the difference hierarchy over NP collapses to level $k$, then the polynomial hierarchy (PH) is equal to the $k$th level of the difference hierarchy over $\Sigma_{2}^{p}$. We simplify their proof and obtain a slightly stronger conclusion: If the difference hierarchy over NP collapses to level $k$, then PH = $\left(P_{(k-1)-tt}^{NP}\right)^{NP}$. We also extend the result to classes other than NP: For any class $C$ that has $\leq_{m}^{p}$-complete sets and is closed under $\leq_{conj}^{p}$and $\leq_{m}^{NP}$-reductions, if the difference hierarchy over $C$ collapses to level $k$, then $PH^{C} = $\left(P_{(k-1)-tt}^{NP}\right)^{C}$. Then we show that the exact counting class $C_{=}P$ is closed under $\leq_{disj}^{p}$and $\leq_{m}^{co-NP}$-reductions. Consequently, if the difference hierarchy over $C_{=}P$ collapses to level $k$ then $PH^{PP}$ is equal to $\left(P_{(k-1)-tt}^{NP}\right)^{PP}$. In contrast, the difference hierarchy over the closely related class PP is known to collapse. Finally, we consider two ways of relativizing the bounded query class $P_{k-tt}^{NP}$: the restricted relativization $P_{k-tt}^{NP^{C}}$, and the full relativization $\left(P_{k-tt}^{NP}\right)^{C}$. If $C$ is NP-hard, then we show that the two relativizations are different unless $PH^{C}$ collapses.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom