Almost-everywhere complexity hierarchies for nondeterministic time (Q1261465)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Almost-everywhere complexity hierarchies for nondeterministic time |
scientific article |
Statements
Almost-everywhere complexity hierarchies for nondeterministic time (English)
0 references
16 September 1993
0 references
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.
0 references
complexity hierarchy
0 references
almost-everywhere complexity
0 references
immunity
0 references
nondeterministic time
0 references
nondeterministic Turing machines
0 references
0 references