Some Descriptive-Set-Theoretical Problems in Complexity Theory

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\in \mathbf{P}[A]$ the uniformizator $U$, is not in $\mathbf{NP}[A]$, 2) there is an oracle $A$ such that $\mathrm{Sep}(\mathbf{NP}[A]$) does not hold and hence so does not $\mathrm{Unif}(\mathbf{coNP}[A])$, and 3) there is an oracle $A$ such that $\mathrm{Sep}(\mathbf{NEXT}[A]$) does not hold and hence so does not $\mathrm{Unif}(\mathbf{coNEXT}[A]$).