Hyper-polynomial hierarchies and the NP-jump
Stephen Fenner, Steven Thomas Homer, Randall J. Pruim, Marcus Schaefer · 2002
Assuming that the polynomial hierarchy (PH) does not collapse, we show the existence of ascending sequences of ptime Turing degrees of length /spl omega//sub 1//sup CK/ all of which are in PSPACE and uniformly hard for PH, such that successors are NP-jumps of their predecessors. This is analogous to the hyperarithmetic hierarchy which is defined similarly but with the (recursive) Turing degrees. The lack of uniform least upper bounds for ascending sequences of ptime degrees causes (the limit levels of) our hyper-polynomial hierarchy to be inherently non-canonical. This problem is investigated in depth, and various possible structures for hyper-polynomial hierarchies are explicated, as are properties of the NP-jump operator on the languages which are in PSPACE but not in PH.