Abstract
We present an a.e. 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 (Author) - Computer Science (New Brunswick)Richard Beigel (Author) - Yale UniversityUlrich Hertrampf (Author) - Bayerische Julius-Maximilians-Universität WürzburgSteven Homer (Author) - Boston University
- Date published
- 1993
- Publisher
- Rutgers University
- Number of pages
- 1 online resource (28 pages)
- Academic Unit
- Computer Science (SAS); School of Arts and Sciences
- Language
- English
- Resource Type
- Technical documentation
- Comment
- Technical report LCSR-TR-189
- Identifiers
- 991031550042204646