Locating P/poly Optimally in the Extended Low Hierarchy
Johannes Köbler
Abstract:
The low hierarchy within NP and the extended low hierarchy have turned out to be very useful in classifying many interesting language classes. We relocate P/poly from the third Sigma-level to the third Theta-level. This location of P/poly inside the extended low hierarchy is optimal since, as shown by Allender and Hemachandra (1992), there exist even sparse sets that are not contained in the next lower level. As a consequence of our result, all NP sets in P/poly are relocated into the third Theta-level of the low hierarchy.
Ps-File: Locating P/poly Optimally in the Extended Low Hierarchy