SHARPLY BOUNDED ALTERNATION AND QUASI-LINEAR TIME

We define the sharply bounded hierarchy, SBH(QL), a hierarchy of class es within P, using quasilinear-time computation and quantification ove r strings of length log n. It generalizes the limited nondeterminism h ierarchy introduced by Buss and Goldsmith, while retaining the invaria nce properties. The new hierarchy has several alternative characteriza tions. We define both SBH(QL) and its corresponding hierarchy of funct ion classes, and present a variety of problems in these classes, inclu ding less than or equal to(m)(ql)-complete problems for each class in SBH(QL). We discuss the structure of the hierarchy, and show that dete rmining its precise relationship to deterministic time classes can imp ly P not equal PSPACE. We present characterizations of SBH(QL) relatio ns based on alternating Turing machines and on first-order definabilit y, as well as recursion-theoretic characterizations of function classe s corresponding to SBH(QL).