The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] immune sets(2hit)

1-2hit
  • The Degrees of Immune and Bi-Immune Sets

    John GESKE  

     
    PAPER-Automata,Languages and Theory of Computing

      Vol:
    E81-D No:6
      Page(s):
    491-495

    We study the pm-degrees and pT-degrees of immune and bi-immune sets. We demonstrate the existence of incomparable pT-immune degrees in deterministic time classes.

  • Nondeterminism, Bi-immunity and Almost-Everywhere Complexity

    John G. GESKE  

     
    PAPER-Algorithm and Computational Complexity

      Vol:
    E76-D No:6
      Page(s):
    641-645

    The main result of this paper is an almost-everywhere hierarchy theorem for nondeterministic space that is as tight as the well-known infinitely-often hierarchy theorems for deterministic and nondeterministic space. In addition, we show that the complexity-theoretic notion of almost-everywhere complex functions is identical to the recursion-theoretic notion of bi-immune sets in the nondeterministic space domain. Finally, we investigate bi-immunity in nondeterministic and alternating time complexity classes and derive a similar hierarchy result for alternating time.