Determining the Levels of Some Special Complexity Classes of Sets in the Kleene Arithmetical Hierarchy
Hisao Tanaka · Tokyo Journal of Mathematics · 1994
We shall determine their levels of some special classes of sets of strings such as $\{X\subseteq\Sigma^* : P[X] eq NP[X]\}$ in the Kleene arithmetical hierarchy on subclasses of $\mathscr{P}(\Sigma^*)$. We shall show that such several classes are proper $\Pi_2^0$, that is, they are $\Pi_2^0$ but not $\Sigma_2^0$.