Computational complexity of the original and extended diophantine Frobenius problem

Abstract

We deduce the law of nonstationary recursion which makes it possible, for given a primitive set A = {a₁,...,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₁,...,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.