С древности алгоритмы неразрывно связаны с математикой. Однако самостоятельное развитие теория алгоритмов получила лишь в первой половине ХХ века. Начальный период был связан с открытием как неразрешимых, так и очень трудных проблем. Например, в 1927 году Габриэль Судан опубликовал первый пример вычислимой функции, которая доказуемо не служит примитивно рекурсивной. Практическое значение асимптотических оценок вычислительной сложности стало очевидным лишь во второй половине ХХ века. Мы рассматриваем некоторые хорошо известные задачи принятия решений, которые можно решить за квазиполиномиальное время, то есть задачи, предположительно принадлежащие к промежуточному классу между полиномиальным и экспоненциальным временем. Коллекция включает в себя проверку изоморфности, вычисление исхода игры на чётность и (обоснованную в предположении справедливости обобщенной гипотезы Римана) факторизацию многочленов от одной переменной над конечными полями. Также представлены некоторые технические результаты, которые могут быть использованы для создания новых алгоритмов квазиполиномиального времени. С. 5-12.
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.
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.
Ключевые слова: квазиполиномиальное время, вычислительная сложность, история.
Keywords: quasipolynomial time, computational complexity, history.
Для пополнения баланса выберите страну, оператора и отправьте СМС с кодом на указанный номер. Отправив одну смс, вы получаете доступ к одной статье.
Закрыть