Punctual categoricity and a jump operation in the primitive recursive degrees
https://doi.org/10.26907/2949-3919.2024.2.47-69
Abstract
The paper is devoted to the study of punctual structures such that any isomorphism between any of its punctual copies is primitive recursively reducible to a fixed 0, 1-valued oracle function. To estimate the complexity of such punctual structures and isomorphisms between them we introduce and investigate the weak (0, 1-valued) jump operation. In the paper we establish that there is a rigid punctual structure for which all isomorphisms are low under the weak jump, and at least one of them is not primitive recursive. Also we construct a rigid punctual structure with every isomorphism reducible to the weak jump of the zero function, and with at least one having a high degree.
Supporting agencies: The work is supported by the grant of the «BASIS» Foundation. Also the results of the first paragraph were performed under the development program of Volga Region Mathematical Center (agreement no. 075-02-2024-1438).
About the Authors
I. Sh. Kalimullin
Kazan Federal University
Russian Federation
Russian Federation
Iskander Shagitovich Kalimullin
Department of Algebra and Mathematical Logic
18 Kremlyovskaya str., Kazan 420008, Russi
A. A. Kurmacheva
Kazan Federal University
Russian Federation
Russian Federation
Alexandra Alekseevna Kurmacheva
Department of Algebra and Mathematical Logic
18 Kremlyovskaya str., Kazan 420008, Russia,
References
1. D. Cenzer, J. Remmel, Polynomial-time abelian groups, Ann. Pure Appl. Log. 56 (1–3), 313–363 (1992). DOI: https://doi.org/10.1016/0168-0072(92)90076-C
2. D. Cenzer, R.G. Downey, J.B. Remmel, Z. Uddin, Space complexity of Abelian groups, Arch. Math. Log. 48 (1), 115–140 (2009). DOI: https://doi.org/10.1007/s00153-008-0113-3
3. I.Sh. Kalimullin, A.G. Melnikov, K.M. Ng, Algebraic structures computable without delay, Theoret. Comput. Sci. 674, 73–98 (2017). DOI: https://doi.org/10.1016/j.tcs.2017.01.029
4. N.A. Bazhenov, R.G. Downey, A.G. Melnikov, I.Sh. Kalimullin, Foundations of online structure theory, Bull. Symb. Log. 25 (2), 141–181 (2019). DOI: https://doi.org/10.1017/bsl.2019.20
5. I.S. Kalimullin, A.G. Melnikov, K.M. Ng, The diversity of categoricity without delay, Algebra Logic 56 (2), 171–177 (2017). DOI: https://doi.org/10.1007/s10469-017-9437-6
6. E.B. Fokina, I. Kalimullin, R. Miller, Degrees of categoricity of computable structures, Arch. Math. Log. 49 (1), 51–67 (2010). DOI: https://doi.org/10.1007/s00153-009-0160-4
7. I.Sh. Kalimullin, A.G. Melnikov, Punctual categoricity relative to a computable oracle, Lobachevskii J. Math. 42 (4), 735–742 (2021). DOI: https://doi.org/10.1134/S1995080221040107
8. R.I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspectives in mathematical logic. Springer-Verlag, Berlin, Heidelberg, New York, etc., 1987. URL: https://link.springer.com/book/9783540666813
9. S.C. Kleene, Extension of an eff ctively generated class of functions by enumeration, Colloq. Math. 6 (1), 68–78 (1958).
10. A. Urquhart, The complexity of decision procedures in relevance logic II, J. Symb. Log. 64 (4), 1774–1802 (1999). DOI: https://doi.org/10.2307/2586811
11. S. Schmitz, Complexity hierarchies beyond elementary, ACM Trans. Comput. Theory, 8 (1), Article 3, 1–36 (2016). DOI: https://doi.org/10.1145/2858784
12. W. Czerwin´ski, L. Orlikowski, Reachability in vector addition systems is Ackermann-complete, 2021 IEEE 62nd Annual symposium on foundations of computer science (FOCS), Denver, CO, USA, 1229–1240 (2022). DOI: https://doi.org/10.1109/FOCS52979.2021.00120
13. J. Leroux, The Reachability problem for Petri nets is not primitive recursive, 2021 IEEE 62nd Annual symposium on foundations of computer science (FOCS), Denver, CO, USA, 1241–1252 (2022). DOI: https://doi.org/10.1109/FOCS52979.2021.00121
14. L. Kristiansen, Information content and computational complexity of recursive sets, G¨odel ’96: Logical foundations of mathematics, computer science and physics – Kurt G¨odel’s legacy. Lecture Notes in Logic, 235–246 (1996). DOI: https://doi.org/10.1017/9781316716939.018
Review
For citations:
Kalimullin I.Sh., Kurmacheva A.A. Punctual categoricity and a jump operation in the primitive recursive degrees. Mathematics and Theoretical Computer Science. 2024;2(2):47-69. (In Russ.) https://doi.org/10.26907/2949-3919.2024.2.47-69
Views:
205
Email this article 