Sharply bounded alternation and quasilinear time

S. A. Bloch, J. F. Buss, J. Goldsmith

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


We define the sharply bounded hierarchy, SBH(QL), a hierarchy of classes within P, using quasilinear-time computation and quantification over strings 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 SBH(QL) and its corresponding hierarchy of function classes, and present a variety of problems in these classes, including ≤qlm-complete problems for each class in SBH(QL). We discuss the structure of the hierarchy, and show that determining its precise relationship to deterministic time classes can imply P ≠ PSPACE. We present characterizations of SBH(QL) relations based on alternating Turing machines and on first-order definability, as well as recursion-theoretic characterizations of function classes corresponding to SBH(QL).

Original languageEnglish
Pages (from-to)187-214
Number of pages28
JournalTheory of Computing Systems
Issue number2
StatePublished - 1998

Bibliographical note

Funding Information:
⁄The first and third authors were supported in part by NSERC Operating Grant OGP0121527 while at the University of Manitoba. The third author was also supported in part by National Science Foundation Grant CCR-9315354. The second author’s work was supported in part by grants from the Natural Sciences and Engineering Research Council (NSERC) of Canada and the Information Technology Research Centre (an Ontario Centre of Excellence).

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics


Dive into the research topics of 'Sharply bounded alternation and quasilinear time'. Together they form a unique fingerprint.

Cite this