Title: Almost-Everywhere Complexity Hierarchies for Nondeterministic Time

Authors: Eric Allender, Richard Beigel, Ulrich Hertrampf, and Steven Homer

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.

Download Full Paper