An NL hierarchy

Jianer Chen, Jim Cox, Bud Mishra

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)21-26
Number of pages6
JournalInformation Processing Letters
Issue number1
StatePublished - Jul 12 1991


  • Computational complexity
  • nondeterministic computation
  • query machines
  • space-bounded computation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'An NL hierarchy'. Together they form a unique fingerprint.

Cite this