Sharply bounded alternation and quasilinear time

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

doi:10.1007/s002240000085

Sharply bounded alternation and quasilinear time

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

Producción científica: Article › revisión exhaustiva

4 Citas (Scopus)

Resumen

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 ≤^ql_m-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).

Idioma original	English
Páginas (desde-hasta)	187-214
Número de páginas	28
Publicación	Theory of Computing Systems
Volumen	31
N.º	2
DOI	https://doi.org/10.1007/s002240000085
Estado	Published - 1998

Nota bibliográfica

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

Financiación

⁄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).

Financiadores	Número del financiador
Information Technology Research Centre
National Science Foundation (NSF)	CCR-9315354
University of Manitoba
Natural Sciences and Engineering Research Council of Canada	OGP0121527

ASJC Scopus subject areas

Theoretical Computer Science
Computational Theory and Mathematics

Acceder al documento

10.1007/s002240000085

Otros archivos y enlaces

Citar esto

@article{f9c3bc3d4ede483490a90310e89e4e19,

title = "Sharply bounded alternation and quasilinear time",

abstract = "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).",

author = "Bloch, \{S. A.\} and Buss, \{J. F.\} and J. Goldsmith",

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{\textquoteright}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).",

year = "1998",

doi = "10.1007/s002240000085",

language = "English",

volume = "31",

pages = "187--214",

number = "2",

}

TY - JOUR

T1 - Sharply bounded alternation and quasilinear time

AU - Bloch, S. A.

AU - Buss, J. F.

AU - Goldsmith, J.

N1 - 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).

PY - 1998

Y1 - 1998

N2 - 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).

AB - 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).

UR - https://www.scopus.com/pages/publications/0032394741

UR - https://www.scopus.com/pages/publications/0032394741#tab=citedBy

U2 - 10.1007/s002240000085

DO - 10.1007/s002240000085

M3 - Article

AN - SCOPUS:0032394741

SN - 1432-4350

VL - 31

SP - 187

EP - 214

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 2

ER -

Sharply bounded alternation and quasilinear time

Resumen

Nota bibliográfica

Financiación

ASJC Scopus subject areas

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto