Loading...
Please wait, while we are loading the content...
Similar Documents
A relationship between difference hierarchies and relativized polynomial hierarchies (1991).
| Content Provider | CiteSeerX |
|---|---|
| Author | Beigel, Richard Chang, Richard Ogiwara Ogiwara, Mitsunori |
| Abstract | Chang and Kadin have shown that if the difference hierarchy over NP collapses to level k, then the polynomial hierarchy (PH) is equal the kth level of the difference hierarchy over p 2 . We simplify their proof and obtain a slightly stronger conclusion: If the difference hierarchy over NP collapses to level k, then PH collapses to P NP (k 1)-tt NP , the class of sets recognized in polynomial time with k 1 nonadaptive queries to a set in NP NP and an unlimited number of queries to a set in NP. We also extend the result to classes other than NP: For any class C that has p m -complete sets and is closed under p conj - and NP m -reductions (alternatively, closed under p disj - and co-NP m -reductions), if the difference hierarchy over C collapses to level k, then PH C = P NP (k 1)-tt C . Then we show that the exact counting class C=P is closed under p disj - and co-NP m - reductions. Consequently, if the difference hierarchy over C=P collap... |
| File Format | |
| Publisher Date | 1991-01-01 |
| Access Restriction | Open |
| Subject Keyword | Difference Hierarchy Relativized Polynomial Hierarchy Co-np Reduction Np Reduction Polynomial Hierarchy Tt Np Exact Counting Class Nonadaptive Query Complete Set Polynomial Time Ph Np Unlimited Number Np Np Kth Level |
| Content Type | Text |
