Abstract
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.