Show simple item record

dc.contributor.authorBeigel, Richarden_US
dc.contributor.authorChang, Richarden_US
dc.contributor.authorOgiwara, Mitsunorien_US
dc.date.accessioned2007-04-23T17:51:45Z
dc.date.available2007-04-23T17:51:45Z
dc.date.issued1991-01en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR91-1184en_US
dc.identifier.urihttps://hdl.handle.net/1813/7024
dc.description.abstractChang 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.en_US
dc.format.extent1465466 bytes
dc.format.extent320389 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleA Relationship between Difference Hierarchies and Relativized Polynomial Hierarchies.en_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics