Nondeterminism, Bi-immunity and Almost-Everywhere Complexity
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E76-D No.6 pp.641-645
- Publication Date
- 1993/06/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Algorithm and Computational Complexity
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
John G. GESKE, "Nondeterminism, Bi-immunity and Almost-Everywhere Complexity" in IEICE TRANSACTIONS on Information,
vol. E76-D, no. 6, pp. 641-645, June 1993, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e76-d_6_641/_p
Copy
@ARTICLE{e76-d_6_641,
author={John G. GESKE, },
journal={IEICE TRANSACTIONS on Information},
title={Nondeterminism, Bi-immunity and Almost-Everywhere Complexity},
year={1993},
volume={E76-D},
number={6},
pages={641-645},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={June},}
Copy
TY - JOUR
TI - Nondeterminism, Bi-immunity and Almost-Everywhere Complexity
T2 - IEICE TRANSACTIONS on Information
SP - 641
EP - 645
AU - John G. GESKE
PY - 1993
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E76-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 1993
AB - 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.
ER -
English
