Publications of the Research Institute for Mathematical Sciences


Full-Text PDF (1538 KB) | Metadata | Table of Contents | PRIMS summary
Volume 28, Issue 4, 1992, pp. 603–614
DOI: 10.2977/prims/1195168210

Published online: 1992-08-31

Some Descriptive-Set-Theoretical Problems in Complexity Theory

Hisao Tanaka[1]

(1) Hosei University, Tokyo, Japan

We bring some descriptive-set- theoretical problems into complexity theory. We here deal with the imiformization problem and the separation problem. It is shown that 1) there exists an oracle A such that for some set SP[A] the uniformizator U, is not in NP[A], 2) there is an oracle A such that Sep (NP[A]) does not hold and hence so does not Unif (coNP[A[), and 3) there is an oracle A such that Sep(NEXT[A]) does not hold and hence so does not Unif(coNEXT[A]).

No keywords available for this article.

Tanaka Hisao: Some Descriptive-Set-Theoretical Problems in Complexity Theory. Publ. Res. Inst. Math. Sci. 28 (1992), 603-614. doi: 10.2977/prims/1195168210