Computational complexity of the original and extended Diophantine Frobenius problem

V. M. Fomichev

Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 3, pp. 104-124

Résumé

We deduce the law of nonstationary recursion which makes it possible, for given a primitive set $A = \{a_1,\ldots,a_k\}$, $k>2$, to construct an algorithm for finding the set of the numbers outside the additive semigroup generated by $A$. In particular, we obtain a new algorithm for determining the Frobenius numbers $g(a_1,\ldots,a_k)$. The computational complexity of these algorithms is estimated in terms of bit operations. We propose a two-stage reduction of the original primitive set to an equivalent primitive set that enables us to improve complexity estimates in the cases when the two-stage reduction leads to a substantial reduction of the order of the initial set. Bibliogr. 16.

Détail

Keywords: Frobenius number, primitive set, additive semigroup, computational complexity.