О вычислительной сложности оригинальной и расширенной диофантовой проблемы Фробениуса

Выведен закон нестационарной рекурсии, позволяющий для любого примитивного множества $A=\{a_1,\ldots,a_k\}$, $k>2$, построить алгоритм определения множества чисел $C(a_1,\ldots,a_k)$, не содержащихся в аддитивной полугруппе, порождённой множеством $A$. В частности, получен новый алгоритм определения чисел Фробениуса $g(a_1,\ldots,a_k)$. Оценена вычислительная сложность алгоритмов в битовых операциях. Предложена двухэтапная редукция исходного примитивного множества в эквивалентное примитивное множество, позволяющая улучшить оценки сложности в тех случаях, когда двухэтапная редукция приводит к существенному сокращению порядка исходного множества. Библиогр. 16.