Existence and uniqueness of structures computable in polynomial time. (English. Russian original) Zbl 1361.03042
Algebra Logic 55, No. 1, 72-76 (2016); translation from Algebra Logika 55, No. 1, 106-112 (2016).
MSC:
| 03D45 | Theory of numerations, effectively presented structures |
| 03C57 | Computable structure theory, computable model theory |
References:
| [1] | D. Cenzer and J. B. Remmel, “Complexity and categoricity,” Inf. Comput., 140, No. 1, 2-25 (1998). · Zbl 0892.68045 · doi:10.1006/inco.1997.2676 |
| [2] | D. Cenzer and J. Remmel, “Polynomial-time versus recursive models,” Ann. Pure Appl. Log., 54, No. 1, 17-58 (1991). · Zbl 0756.03021 · doi:10.1016/0168-0072(91)90008-A |
| [3] | D. Cenzer and J. Remmel, “Polynomial-time abelian groups,” Ann. Pure Appl. Log., 56, Nos. 1-3, 313-363 (1992). · Zbl 0764.03015 |
| [4] | D. Cenzer and J. B. Remmel, “Complexity theoretic model theory and algebra,” in Handbook of Recursive Mathematics, Vol. 1, Recursive Model Theory, Stud. Logic Found. Math., 138, Yu. L. Ershov et al. (eds.), Elsevier, Amsterdam (1998), pp. 381-513. · Zbl 0941.03035 |
| [5] | E. I. Latkin, “Polynomial non-autostability. Algebraic approach,” in Logical Methods in Programming, Vychislitel’nye Systemy, 133, Sobolev Institute of Mathematics, Novosibirsk (1990), pp. 14-37. · Zbl 0754.03026 |
| [6] | E. I. Latkin, “An abstract functional that bounds the algorithmic complexity for linear, polynomial, and other similar classes,” in Vychislitel’nye Systemy, 165, Sobolev Institute of Mathematics, Novosibirsk (1999), pp. 84-111. · Zbl 0952.03049 |
| [7] | S. S. Goncharov, “Algorithmic dimension of Abelian groups,” Proc. 17th All-Union Alg. Conf., Part 2, Minsk (1983). |
| [8] | S. T. Fedoryaev, “Recursively inconsistent algorithmic problems on 1-constructivizable relatively complemented distributive lattices,” Algebra and Logic, 34, No. 6, 371-378 (1995). · Zbl 0897.03048 |
| [9] | S. T. Fedoryaev, “Countability of widths of algebraic reducibility structures for models in some classes,” Sib. Adv. Math., 3, No. 2, 81-103 (1993). · Zbl 0847.03019 |
| [10] | B. M. Khusainov, “Algorithmic degree of unars,” Algebra and Logic, 27, No. 4, 301-312 (1988). · Zbl 0684.03012 |
| [11] | O. V. Kudinov, “Algebraic dependences and reducibilities of constructivizations in universal domains,” Tr. Inst. Mat. SO RAN, 25, 74-81 (1993). · Zbl 0849.03024 |
| [12] | D. V. Lytkina, “Algebraically nonequivalent constructivization for infinite-dimensional vector space,” Algebra and Logic, 29, No. 6, 430-440 (1990). · Zbl 0786.03024 |
| [13] | V. A. Uspensky and A. L. Semenov, “Algorithm theory: Contributions and applications,” in Algorithms in Modern Mathematics and Its Applications [in Russian], Part 1, Computer Center SO AN SSSR, Novosibirsk (1982), pp. 99-342. · Zbl 0583.68008 |
| [14] | V. A. Uspensky and A. L. Semenov, Algorithm Theory: Contributions and Applications, Nauka, Moscow (1987). |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
