Almost-everywhere complexity hierarchies for nondeterministic time

Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer

Research output: Contribution to journalArticle

12 Scopus citations

Abstract

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
Volume115
Issue number2
DOIs
StatePublished - Jul 19 1993

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this