Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR96-011 | 29th January 1996 00:00

#### Sharply Bounded Alternation within P

TR96-011
Authors: Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith
Publication: 9th February 1996 20:32
Keywords:

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.

ISSN 1433-8092 | Imprint