期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
