Abstract:
We define the sharply bounded hierarchy, SBHQL, a hierarchy of classes within P, using quasilinear-time computation and quantification over values of length log n. It generalizes the limited nondeterminism hierarchy introduced by Buss and Goldsmith, while retaining the invariance properties. The new hierarchy has several alternative characterizations. We define both SBHQL and its corresponding hierarchy of function classes, FSBHQL, and present a variety of problems in these classes, including $\complete problems for each class in SBHQL. We discuss the structure of the hierarchy, and show that certain simple structural conditions on it would imply P not equal to PSPACE. We present characterizations of {\sbhql} relations based on alternating Turing machines and on first-order definability, as well as recursion-theoretic characterizations of function classes corresponding to SBHQL.