Almost-everywhere complexity hierarchies for nondeterministic time

From MaRDI portal





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.











This page was built for publication: Almost-everywhere complexity hierarchies for nondeterministic time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1261465)