TY - JOUR
AU - Alexandr Vladislavovich Seliverstov
PY - 2021/08/15
Y2 - 2024/08/12
TI - On some quasipolynomial-time algorithms
JF - Computer Tools in Education
JA - CTE
VL -
IS - 2
SE - Algorithmic mathematics and mathematical modelling
DO - 10.32603/2071-2340-2021-2-5-12
UR - http://cte.eltech.ru/ojs/index.php/kio/article/view/1684
AB - 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 20thcentury. 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.
ER -