P-m-Mitotic Sets and Arithmetical Hierarchy
DOI:
https://doi.org/10.51408/1963-0114Keywords:
Arithmetical hierarchy, P-m-mitotic set, P-m-autoreducible set, index setAbstract
References
H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967.
R.I. Soare, Recursively Enumerable Sets and Degree: A study of computable functions and computably generated sets, Perspectives in Mathematical Logic, Springer-Verlag, 1987.
R.M. Karp, “Reducibility among combinatorial problems” , in Complexity of Computer Computations, R.E. Miller and J.M. Thatcher, Eds, Plenum, New York, pp. 85-103, 1972
S. A. Cook, “The complexity of theorem proving procedures,” Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151-158, 1971.
R.E. Ladner, “On the Structure of Polynomial Time Reducibility,” Journal of the Association for Computing Machinery, vol. 22, no. 1, pp. 155-171, 1975.
K. Ambos-Spies, Part of the book series: Lecture Notes in Computer Science: P-mitotic sets, Logic and Machines: Decision Problems and Complexity Proceedings of the Symposium on Recursive Combinatorics, vol. 171, pp. 1-23, 1983.
J. E. Hopcroft, J. D. Ullman, Introduction to Automata theory, Languages and Computation, Addison-Wesley Publishing Company, 1979.
M. Sipser, Introduction to the Theory of Computation, PWS, Boston, MA, 1996.
S. Arora and B. Barak, Computational Complexity, A Modern Approach, Cambridge University Press, 2009.
S. A. Terwijn, Complexity Theory, Nijmegen, the Netherlands, 2010.
B.L. van der Waerden, Algebra, Springer, vol. 1, 2003 (vol. 1 is translated from the German Algebra I, seventh edition, Springer-Verlag Berlin, 1966).
A.H. Mokatsian, “Polynomial Time Turing Mitoticity and Arithmetical Hierarchy”, Pattern Recognition and Image Analysis, Pleiades Publishing , vol. 34, no. 1, pp. 9–19. 2024.
R.G. Downey and M. Stob, “Splitting Theorems In Recursion Theory,” Ann. Pure Appl. Logic, vol. 65, pp. 1-106, 1993.
A.H. Lachlan, “The priority method. I,” Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 13, pp. 1–10, 1967.
B. Trakhtenbrot, “On autoreducibility,” Dokl. Akad. Nauk SSSR, vol. 192, pp. 1224–1227, 1970 (in Russian).
R.E. Ladner, “Mitotic recursively enumerable sets,” J. Symb. Log., vol. 38, pp. 199–211, 1973.
R.G. Downey and T.A. Slaman, “Completely mitotic r.e. degrees,” Ann. Pure Appl. Logic, vol. 41, no.2, pp. 119–152, 1989.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Arsen H. Mokatsian and Khachatur А. Barseghyan
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
