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.
- Title
- Almost-everywhere complexity hierarchies for nondeterministic time
- Creators
- Eric Allender - Department of Computer Science, Rutgers University, New Brunswick, NJ 08903, USARichard Beigel - Department of Computer Science, Yale University, 51 Prospect St., P.O. Box 2158, Yale Station, New Haven, CT 06520-2158, USAUlrich Hertrampf - Institut für Informatik, Universität Würzburg, D-8700 Würzburg, GermanySteven Homer - Department of Computer Science, Boston University, Boston, MA 02215, USA
- Publication Details
- Theoretical computer science, Vol.115(2), pp.225-241
- Date published
- 1993
- Publisher
- Elsevier B.V
- Academic Unit
- Computer Science (SAS)
- Language
- English
- Resource Type
- Journal article
- Identifiers
- 991031654807304646