On some quasipolynomial-time algorithms
Abstract
Since ancient times, algorithms are inextricably linked with mathematics. However, the theory of algorithms received independent development only in the first half of the 20th century. The initial period was associated with discovery of unsolvable as well as very difficult problems. So, in 1927 Gabriel Sudan published the first example of a computable function that is provably not primitive recursive. The practical significance of asymptotic estimates of computational complexity became apparent only in the second half of the 20th
century. We consider some well-known decision problems solvable in quasipolynomial time, that is, problems presumably belonging to the intermediate class between polynomial time and exponential time. The collection comprises isomorphism testing, solution to the parity game, and (validated under the generalized Riemann hypothesis) factorization of univariate polynomials over finite fields. We also present some technical results, which can be used to create new quasipolynomial-time algorithms.
References
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).
This work is licensed under a Creative Commons Attribution 4.0 International License.
