О некоторых алгоритмах квазиполиномиального времени

Александр Владиславович Селиверстов

doi:10.32603/2071-2340-2021-2-5-12

Александр Владиславович Селиверстов Институт проблем передачи информации им. А. А. Харкевича Российской академии наук, Большой Каретный пер., д. 19, стр. 1, 127051, Москва, Россия https://orcid.org/0000-0003-4746-6396

DOI: https://doi.org/10.32603/2071-2340-2021-2-5-12

Ключевые слова: многочлен, квазиполиномиальное время, вычислительная сложность, история

Аннотация

С древности алгоритмы неразрывно связаны с математикой. Однако самостоятельное развитие теория алгоритмов получила лишь в первой половине ХХ века. Начальный период был связан с открытием как неразрешимых, так и очень трудных проблем. Например, в 1927 году Габриэль Судан опубликовал первый пример вычислимой функции, которая доказуемо не служит примитивно рекурсивной. Практическое значение асимптотических оценок вычислительной сложности стало очевидным лишь во второй половине ХХ века. Мы рассматриваем некоторые хорошо известные задачи принятия решений, которые можно решить за квазиполиномиальное время, то есть задачи, предположительно принадлежащие к промежуточному классу между полиномиальным и экспоненциальным временем. Коллекция включает в себя проверку изоморфности, вычисление исхода игры на чётность и (обоснованную в предположении справедливости обобщенной гипотезы Римана) факторизацию многочленов от одной переменной над конечными полями. Также представлены некоторые технические результаты, которые могут быть использованы для создания
новых алгоритмов квазиполиномиального времени.

Биография автора

Александр Владиславович Селиверстов, Институт проблем передачи информации им. А. А. Харкевича Российской академии наук, Большой Каретный пер., д. 19, стр. 1, 127051, Москва, Россия

Кандидат физико-математических наук, ведущий научный сотрудник Института проблем передачи информации им. А. А. Харкевича Российской академии наук, slvstv@iitp.ru

Литература

C. Calude, S. Marcus, and I. Tevy, “The first example of a recursive function which is not primitive recursive,” Historia Mathematica, vol. 6, no. 4, pp. 380–384, 1979; doi: 10.1016/0315-0860(79)90024-7

G. Sudan, “Sur le nombre transfini ω^ω,” Bulletin Mathematique de la Societe Roumaine des Sciences , vol. 30, no. 1, pp. 11–30, 1927. [Online]. Available: https://www.jstor.org/stable/43769875

W. Ackermann, “Zum Hilbertschen Aufbau der reellen Zahlen,” Mathematische Annalen, vol. 99, no. 1, pp. 118–133, 1928; doi: 10.1007/BF01459088

A. Cobham, “The intrinsic computational difficulty of functions,” Y. Bar-Hillel ed., in Logic, Methodology and Philosophy of Science. Proc. Intern. Congress 1964. North-Holland, Amsterdam, 1965, pp. 24–30. [Online]. Available: https://www.cs.toronto.edu/~sacook/homepage/cobham_intrinsic.pdf

J. Edmonds, “Paths, trees, and flowers,” Canadian Journal of Mathematics, vol. 17, pp. 449–467, 1965; doi: 0.4153/CJM-1965-045-4

S. A. Cook, “The complexity of theorem-proving procedures,” in Proc. of Third Annual ACM Symposium on Theory of Computing (Shaker Heights, Ohio, 1971), ACM, N. Y., 1971, pp. 151–158.

L. A. Levin, “Universal sequential search problems,” Problems of Information Transmission, vol. 9, no. 3, pp. 265–266, 1973.

S. V. Soloviev, “Destinies and Seminars (On the Seminar ‘Problems of Reducing the Exhaustive Search’ at LETI in a Historical and Scientific Context),” Computer tools in education, no. 4, pp. 5–14, 2019 (in Russian); doi: 10.32603/2071-2340-2019-4-5-14

A. M. Kotochigov and A. I. Suchkov, “A method for reducing iteration in algorithms for building minimal additive chains,” Computer Tools in Education, no. 1, pp. 5–18, 2020 (in Russian); doi: 10.32603/2071-2340-2020-1-5-18

F. Karteszi, ˊ Introduction to finite geometries, Budapest: Akademiai Kiado, 1976.

N. D. Gogin and A. A. Myll¨ari, “On computer modeling of finite-generated free projective planes,” Computer tools in education, no. 4, pp. 14–28, 2017.

R. J. Lipton, L. Snyder and Y. Zalcstein, The complexity of word and isomorphism problems for finite groups (Preliminary report), [Research Report], no. 91, Yale University, 1977. [Online]. Available: https://archive.org/details/DTIC_ADA053246

D. J. Rosenbaum, “Breaking the n^(log n) barrier for solvable-group isomorphism,” in SODA 2013: Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms. ACM-SIAM, New Orleans Louisiana, 2013, pp. 1054–1073; doi: 10.5555/2627817.2627893

L. Babai, P. Codenotti, and Y. Qiao, “Polynomial-time isomorphism test for groups with no abelian normal subgroups,” A. Czumaj, K. Mehlhorn, A. Pitts, and R. Wattenhofer, eds. in Automata, Languages, and Programming. ICALP 2012. Lecture Notes in Computer Science, vol 7391, Berlin, Heidelberg: Springer, 2012, pp. 51–62; doi: 10.1007/978-3-642-31594-7_5

T. Kavitha, “Linear time algorithms for abelian group isomorphism and related problems,” Journal of Computer and System Sciences, vol. 73, no. 6, pp. 986–996, 2007.

G. L. Miller, “On the n^(log n) isomorphism technique (A preliminary report),” in STOC 1978: Proceedings of the tenth annual ACM symposium on Theory of computing. ACM, New York, NY, USA, 1978, pp. 51–58; doi: 10.1145/800133.804331

S. A. Evdokimov and I. N. Ponomarenko, “On the geometric graph isomorphism problem,” Journal of Pure and Applied Algebra, vol. 117-118, pp. 253–276, 1997; doi: 10.1016/S0022-4049(97)00014-5

L. Babai and J. Wilmes, “Quasipolynomial-time canonical form for steiner designs,” in STOC 2013: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing. ACM, New York, NY, USA, 2013, pp. 261–270; doi: 10.1145/2488608.2488642

X. Chen, X. Sun, and S.-H. Teng, “Multi-stage design for quasipolynomial-time isomorphism testing of Steiner 2-systems,” in STOC 2013: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing. ACM, New York, NY, USA, 2013, pp. 271–280; doi: 10.1145/2488608.2488643

C. S. Calude, S. Jain, B. Khoussainov, and W. Li, F. Stephan, “Deciding parity games in quasipolynomial time,” in STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. ACM, New York, NY, USA, 2017, pp. 252–263; doi: 10.1145/3055399.3055409

C. S. Calude, S. Jain, B. Khoussainov, and W. Li, F. Stephan, “Deciding parity games in quasi-polynomial time,” SIAM Journal on Computing, pp. STOC17-152-STOC17-188, 2020; doi: 10.1137/17M1145288

J. Fearnley, S. Jain, B. de Keijzer, S. Schewe, F. Stephan, and D. Wojtczak, “An ordered approach to solving parity games in quasi-polynomial time and quasi-linear space,” International Journal on Software Tools for Technology Transfer, vol. 21, pp. 325–349, 2019; doi: 10.1007/s10009-019-00509-3

M. Jurdzinski, “Deciding the winner in parity games is in ˊ UP ∩co −UP,” Information Processing Letters, vol. 68, no. 3, pp. 119–124, 1998; doi: 10.1016/S0020-0190(98)00150-1

S. Evdokimov, “Factorization of polynomials over finite fields in subexponential time under GRH,” L. M. Adleman and M.-D. Huang, eds, in Algorithmic Number Theory. ANTS 1994. Lecture Notes in Computer Science, vol. 877, 1994, pp. 209–219; doi: 10.1007/3-540-58691-1_58

E. R. Berlekamp, “Factoring polynomials over large finite fields,” Mathematics of Computation, vol. 24, no. 111, pp. 713–735, 1970; doi: 10.2307/2004849

V. V. Prasolov, Polynomials, Berlin: Springer, 2004; doi: 10.1007/978-3-642-03980-5

L. M. Adleman, C. Pomerance, and R. S. Rumely, “On distinguishing prime numbers from composite numbers,” Annals of Mathematics, vol. 117, no. 1, pp. 173–206, 1983.

M. Agrawal, N. Kayal, and N. Saxena, “PRIMES is in P,” Annals of Mathematics, vol. 160, no. 2, pp. 781–793, 2004; doi: 10.4007/annals.2004.160.781

A. A. Buchstab, The number theory, Moscow: Prosveshchenie publ., 1966 (in Russian).