Geodesic
Computational complexity of the original and extended Diophantine Frobenius problem
Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 3, pp. 104-124.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: Frobenius number, primitive set, additive semigroup, computational complexity. 
@article{DA_2017_24_3_a5,
     author = {V. M. Fomichev},
     title = {Computational complexity of the original and extended {Diophantine} {Frobenius} problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {104--124},
     publisher = {mathdoc},
     volume = {24},
     number = {3},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2017_24_3_a5/}
}
TY  - JOUR
AU  - V. M. Fomichev
TI  - Computational complexity of the original and extended Diophantine Frobenius problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2017
SP  - 104
EP  - 124
VL  - 24
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2017_24_3_a5/
LA  - ru
ID  - DA_2017_24_3_a5
ER  - 
%0 Journal Article
%A V. M. Fomichev
%T Computational complexity of the original and extended Diophantine Frobenius problem
%J Diskretnyj analiz i issledovanie operacij
%D 2017
%P 104-124
%V 24
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2017_24_3_a5/
%G ru
%F DA_2017_24_3_a5
V. M. Fomichev. Computational complexity of the original and extended Diophantine Frobenius problem. Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 3, pp. 104-124. http://geodesic.mathdoc.fr/item/DA_2017_24_3_a5/

[1] V. I. Arnold, Experimental observation of mathematical facts, MTsNMO, M., 2006

[2] A. V. Ustinov, “The solution of Arnold's problem on the weak asymptotics of Frobenius numbers with three arguments”, Sb. Math., 200:4 (2009), 597–627 | DOI | DOI | MR | Zbl

[3] A. V. Ustinov, “Geometric proof of Rødseth's formula for Frobenius numbers”, Proc. Steklov Inst. Math., 276:1 (2012), 275–282 | DOI | MR | Zbl

[4] V. M. Fomichev, “Primitive sets of numbers being equivalent by Frobenius”, Prikladn. Diskretn. Mat., 2014, no. 1, 20–26

[5] V. M. Fomichev, “Estimates for exponent of some graphs by means of Frobenius's numbers of three arguments”, Prikladn. Diskretn. Mat., 2014, no. 2, 88–96

[6] Böcker S., Lipták Zs., “The Money Changing Problem revisited: Computing the Frobenius number in time $O(ka_1)$”, Computing and Combinatorics, Proc. 4th Annu. Int. Conf. (Kunming, China, Aug. 16–19, 2005), Lect. Notes Comput. Sci., 3595, Springer, Heidelberg, 2005, 965–974 | DOI | MR | Zbl

[7] Bogart C., Calculating Frobenius numbers with Boolean Toeplitz matrix multiplication, , 2009 (accessed Mar. 10, 2017) http://quetzal.bogarthome.net/frobenius.pdf

[8] Brauer A., “On a problem of partitions”, Am. J. Math., 64 (1942), 299–312 | DOI | MR | Zbl

[9] Brauer A., Shockley J. E., “On a problem of Frobenius”, J. Reine Angew. Math., 211 (1962), 215–220 | MR | Zbl

[10] Curtis F., “On formulas for the Frobenius number of a numerical semigroup”, Math. Scand., 67 (1990), 190–192 | DOI | MR | Zbl

[11] Heap B. R., Lynn M. S., “A graph-theoretic algorithm for the solution of a linear Diophantine problem of Frobenius”, Numer. Math., 6 (1964), 346–354 | DOI | MR | Zbl

[12] Heap B. R., Lynn M. S., “On a linear Diophantine problem of Frobenius: an improved algorithm”, Numer. Math., 7 (1965), 226–231 | DOI | MR | Zbl

[13] Johnson D. B., “Efficient algorithms for shortest paths in space networks”, JACM, 24 (1977), 1–13 | DOI | MR | Zbl

[14] Nijenhuis M., “A minimal-path algorithm for the “Money changing problem””, Am. Math. Mon., 86 (1979), 832–835 | DOI | MR | Zbl

[15] Ramírez Alfonsín J. L., The Diophantine Frobenius problem, Oxf. Lect. Ser. Math. Appl., 30, Clarendon Press, Oxford, 2005, 243 pp. | MR

[16] Sylvester J. J., “Problem 7382”, Mathematical Questions with Their Solutions, Educational Times, 41, Francis Hodgson, London, 1884, 21 (Accessed Mar. 10, 2017) http://archive.org/stream/mathematicalque05unkngoog#page/n150/mode/2up