首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号