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 such that for some set the uniformizator , is not in , 2) there is an oracle such that ) does not hold and hence so does not , and 3) there is an oracle such that ) does not hold and hence so does not ).

Cite this article

Hisao Tanaka, Some Descriptive-Set-Theoretical Problems in Complexity Theory. Publ. Res. Inst. Math. Sci. 28 (1992), no. 4, pp. 603–614

DOI 10.2977/PRIMS/1195168210