Computational complexity of the original and extended diophantine Frobenius problem |
| |
Authors: | V M Fomichev |
| |
Institution: | 1.Financial University under the Government of the Russian Federation,Moscow,Russia;2.National Research Nuclear University MEPhI,Moscow,Russia |
| |
Abstract: | We deduce the law of nonstationary recursion which makes it possible, for given a primitive set A = {a 1,...,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,...,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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|