# Some Descriptive-Set-Theoretical Problems in Complexity Theory

### Hisao Tanaka

Hosei University, Tokyo, Japan

## Abstract

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*]).