An NL hierarchy

Jianer Chen; Jim Cox; Bud Mishra

doi:10.1016/0020-0190(91)90057-O

An NL hierarchy

Jianer Chen, Jim Cox, Bud Mishra

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

We introduce a new nondeterministic oracle model. Our model is significantly different from all previous space-bounded oracle models, and has the following properties: First, it permits a nontrivial NL-hierarchy, which does not collapse without a similar consequence for the polynomial-time hierarchy. This is immediate from the result that ∑ k p is exactly the 2kth level in our NL-hierarchy, for all k≥1. On the other hand, it still behaves very well in relativised worlds. In particular, the new model satisfies the Immerman-Szelepcsenyi theorem and Savitch's theorem in the relativized worlds for oracle sets in each level of the polynomial-time hierarchy.

Original language	English (US)
Pages (from-to)	21-26
Number of pages	6
Journal	Information Processing Letters
Volume	39
Issue number	1
DOIs	https://doi.org/10.1016/0020-0190(91)90057-O
State	Published - Jul 12 1991

Keywords

Computational complexity
nondeterministic computation
query machines
space-bounded computation

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/0020-0190(91)90057-O

Cite this

@article{7197b3abe7a449a9a19542344a30f26c,

title = "An NL hierarchy",

abstract = "We introduce a new nondeterministic oracle model. Our model is significantly different from all previous space-bounded oracle models, and has the following properties: First, it permits a nontrivial NL-hierarchy, which does not collapse without a similar consequence for the polynomial-time hierarchy. This is immediate from the result that ∑ k p is exactly the 2kth level in our NL-hierarchy, for all k≥1. On the other hand, it still behaves very well in relativised worlds. In particular, the new model satisfies the Immerman-Szelepcsenyi theorem and Savitch's theorem in the relativized worlds for oracle sets in each level of the polynomial-time hierarchy.",

keywords = "Computational complexity, nondeterministic computation, query machines, space-bounded computation",

author = "Jianer Chen and Jim Cox and Bud Mishra",

note = "Funding Information: * Supported in part by Engineering Excellence Award from Texas A&M University. Funding Information: * * Supported in part by PSC-CUNY 669287. Copyright: Copyright 2014 Elsevier B.V., All rights reserved.",

year = "1991",

month = jul,

day = "12",

doi = "10.1016/0020-0190(91)90057-O",

language = "English (US)",

volume = "39",

pages = "21--26",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - An NL hierarchy

AU - Chen, Jianer

AU - Cox, Jim

AU - Mishra, Bud

N1 - Funding Information: * Supported in part by Engineering Excellence Award from Texas A&M University. Funding Information: * * Supported in part by PSC-CUNY 669287. Copyright: Copyright 2014 Elsevier B.V., All rights reserved.

PY - 1991/7/12

Y1 - 1991/7/12

N2 - We introduce a new nondeterministic oracle model. Our model is significantly different from all previous space-bounded oracle models, and has the following properties: First, it permits a nontrivial NL-hierarchy, which does not collapse without a similar consequence for the polynomial-time hierarchy. This is immediate from the result that ∑ k p is exactly the 2kth level in our NL-hierarchy, for all k≥1. On the other hand, it still behaves very well in relativised worlds. In particular, the new model satisfies the Immerman-Szelepcsenyi theorem and Savitch's theorem in the relativized worlds for oracle sets in each level of the polynomial-time hierarchy.

AB - We introduce a new nondeterministic oracle model. Our model is significantly different from all previous space-bounded oracle models, and has the following properties: First, it permits a nontrivial NL-hierarchy, which does not collapse without a similar consequence for the polynomial-time hierarchy. This is immediate from the result that ∑ k p is exactly the 2kth level in our NL-hierarchy, for all k≥1. On the other hand, it still behaves very well in relativised worlds. In particular, the new model satisfies the Immerman-Szelepcsenyi theorem and Savitch's theorem in the relativized worlds for oracle sets in each level of the polynomial-time hierarchy.

KW - Computational complexity

KW - nondeterministic computation

KW - query machines

KW - space-bounded computation

UR - http://www.scopus.com/inward/record.url?scp=0026189009&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026189009&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(91)90057-O

DO - 10.1016/0020-0190(91)90057-O

M3 - Article

AN - SCOPUS:0026189009

SN - 0020-0190

VL - 39

SP - 21

EP - 26

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -

An NL hierarchy

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this