Almost-everywhere complexity hierarchies for nondeterministic time

Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


We present an almost-everywhere complexity hierarchy for nondeterministic time, and show that it is essentially the best result of this sort that can be proved using relativizable proof techniques.

Original languageEnglish (US)
Pages (from-to)225-241
Number of pages17
JournalTheoretical Computer Science
Issue number2
StatePublished - Jul 19 1993

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Almost-everywhere complexity hierarchies for nondeterministic time'. Together they form a unique fingerprint.

Cite this