JournalsprimsVol. 28 , No. 4DOI 10.2977/prims/1195168210

Some Descriptive-Set-Theoretical Problems in Complexity Theory

  • Hisao Tanaka

    Hosei University, Tokyo, Japan
Some Descriptive-Set-Theoretical Problems in Complexity Theory cover

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