Polynomial Time Turing Mitoticity and Arithmetical Hierarchy
Arsen H. Mokatsian · Pattern Recognition and Image Analysis · 2024
Let $$\omega $$ be the set of all nonnegative integers. Let P be a class of problems recognized by deterministic Turing machines, which run in polynomial time. It is known that effective enumeration of the sets of the class P (namely, $${{P}_{0}},{{P}_{1}}$$ , …, $${{P}_{i}}$$ , …) exists and thus $${\mathbf{P}} = \{ {{P}_{i}}\,|\,i \in \omega \} .$$ Note that for each $$i$$ , $${{P}_{i}}$$ is a set of strings that are sequences of 0s and 1s. Based on available numbering of computably enumerable (c.e.) sets $${{\{ {{W}_{i}}\} }_{{i \in \omega }}}$$ , a sequence of sets of non-negative numbers $${{\hat {P}}_{i}}$$ is constructed such that there is an effective enumeration of them. Let us define $${\mathbf{\hat {P}}}$$ as follows: $$~{\mathbf{\hat {P}}} = \{ {{\hat {P}}_{i}}\,|\,i \in \omega \} $$ . It’s obvious that it is possible to define such relations between the elements of the set of mentioned strings and between the elements of the set of nonnegative integers that these two sets will be isomorphic (with respect to the relations in question). The article shows that it is possible to define such relations between the elements of $${\mathbf{P}}$$ and between the elements of $$\hat {{\mathbf{P}}}$$ that there will be homomorphic mappings from $${\mathbf{P}}$$ to $$\hat {{\mathbf{P}}}$$ and vice versa, from $$\hat {{\mathbf{P}}}$$ to $${\mathbf{P}}$$ (with respect to the relations in question). Based on the notions of T-mitoticity and T-autoreducibility, Ambos-Spies introduced the notions of P‑T-mitoticity, weakly P-T-mitoticity and P-T-autoreducibility. By analogy with the mentioned notions we introduce the notions of $$\hat {P}$$ -T-mitoticity, weakly $$\hat {P}$$ -T-mitoticity and $$\hat {P}$$ -T-autoreducibility. It is proved in the article that the index sets { $${\text{z}}\,|\,{{{\text{W}}}_{{\text{z}}}}$$ is $${{\hat {P}}}$$ -T-mitotic}, $${\text{\{ z}}\,|\,{{{\text{W}}}_{{\text{z}}}}$$ is weakly $${{\hat {P}}}$$ -T-mitotic}, $${\text{\{ }}~{\text{z}}\,|\,{{{\text{W}}}_{{\text{z}}}}$$ is $${{\hat {P}}}$$ -T-autoreducible} and $${\text{\{ z}}\,|\,{{{\text{W}}}_{{\text{z}}}} \in {\mathbf{\hat {P}}}\} $$ are $${{{\mathbf{\Sigma }}}_{3}}$$ -complete.