Almost-everywhere complexity hierarchies for nondeterministic time (Q1261465)

The ``almost-everywhere complexity'' notion differs from the more common ``infinitely-often'' one in that a set is considered hard if all but a finite number of its elements are hard (as opposite to the existence of just an infinite subset of hard elements). The authors make use of the relation between the almost-everywhere complexity and immunity notions to prove an almost-everywhere complexity hierarchy theorem for nondeterministic time. Moreover they show that their result cannot be improved by using relativizable proof techniques. In addition they consider consistent nondeterministic Turing machines in order to investigate more acceptable notion of almost-everywhere complexity for nondeterministic time and prove a hierarchy theorem for this case as well. Also, in this case their result cannot be improved by relativizable proof techniques.