Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith

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

Ryan Williams

We prove a model-independent non-linear time lower bound for a slight generalization of the quantified Boolean formula problem (QBF). In particular, we give a reduction from arbitrary languages in alternating time t(n) to QBFs describable in O(t(n)) bits by a reasonable (polynomially) succinct encoding. The reduction works for many reasonable ... more >>>