Determining the Levels of Some Special Complexity Classes of Sets in the Kleene Arithmetical Hierarchy

TANAKA, Hisao

TANAKA, Hisao

Tokyo J. of Math., Tome 17 (1994) no. 2, p. 125-133 / Harvested from Project Euclid

Résumé

We shall determine their levels of some special classes of sets of strings such as $\{X\subseteq\Sigma^* : P[X]\neq 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$.

Publié le : 1994-06-15
Classification:

@article{1270128190,
     author = {TANAKA, Hisao},
     title = {Determining the Levels of Some Special Complexity Classes of Sets in the Kleene Arithmetical Hierarchy},
     journal = {Tokyo J. of Math.},
     volume = {17},
     number = {2},
     year = {1994},
     pages = { 125-133},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1270128190}
}

TANAKA, Hisao. Determining the Levels of Some Special Complexity Classes of Sets in the Kleene Arithmetical Hierarchy. Tokyo J. of Math., Tome 17 (1994) no. 2, pp.  125-133. http://gdmltest.u-ga.fr/item/1270128190/