Nondeterminism, Bi-immunity and Almost-Everywhere Complexity

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 一般社団法人電子情報通信学会の論文
• 1993-06-25

著者

• Geske JohnG.

  Department of Computer Science, Michigan State University

関連論文

• Nondeterminism, Bi-immunity and Almost-Everywhere Complexity

スポンサーリンク