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
    0 references
    0 references
    0 references
    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

    Identifiers