Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR96-011 | 29th January 1996 00:00

Sharply Bounded Alternation within P



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

ISSN 1433-8092 | Imprint