# 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 *S*∈**P**[*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