Том 24, номер 3, 2017 г., Стр. 104-124

УДК 519.6
Фомичёв В. М.
О вычислительной сложности оригинальной и расширенной диофантовой проблемы Фробениуса

Аннотация:
Выведен закон нестационарной рекурсии, позволяющий для любого примитивного множества $A = {a_1, . . . , a_k}$, $k > 2$, построить алгоритм определения множества чисел $C(a_1, . . . , a_k)$, не содержащихся в аддитивной полугруппе, порождённой множеством $A$. В частности, получен новый алгоритм определения чисел Фробениуса $g(a_1, . . . , a_k)$. Оценена вычислительная сложность алгоритмов в битовых операциях. Предложена двухэтапная редукция исходного примитивного множества в эквивалентное примитивное множество, позволяющая улучшить оценки сложности в тех случаях, когда двухэтапная редукция приводит к существенному сокращению порядка исходного множества.
Библиогр. 16.

Ключевые слова: число Фробениуса, примитивное множество, аддитивная полугруппа, сложность вычислений.

DOI: 10.17377/daio.2017.24.537

Фомичёв Владимир Михайлович ^1,2
1. Финансовый университет при Правительстве РФ,
Ленинградский пр., 49, 125993 Москва, Россия
2. Национальный исследовательский ядерный университет «МИФИ»,
Каширское шоссе, 31, 115409 Москва, Россия
е-mail: fomichev@nm.ru

Статья поступила 8 апреля 2016 г.
Исправленный вариант — 31 октября 2016 г.

Литература

[1] Арнольд В. И. Экспериментальное наблюдение математических фактов. М.: МЦНМО, 2006. 119 с.

[2] Устинов А. В. Решение задачи Арнольда о слабой асимптотике для чисел Фробениуса с тремя аргументами // Мат. сб. 2009. № 4. С. 131–160.

[3] Устинов А. В. Геометрическое доказательство формулы Рёдсета для чисел Фробениуса // Тр. МИАН. 2012. № 276. С. 280–287.

[4] Фомичёв В. М. Эквивалентные по Фробениусу примитивные множества чисел // Прикл. дискрет. математика. 2014. № 1. С. 20–26.

[5] Фомичёв В. М. Оценка экспонента некоторых графов с помощью чисел Фробениуса для трех аргументов // Прикл. дискрет. математика. 2014. № 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). Heidelberg: Springer, 2005. P. 965–974. (Lect. Notes Comput. Sci.; Vol. 3595).

[7] Bogart C. Calculating Frobenius numbers with Boolean Toeplitz matrix multiplication. http://quetzal.bogarthome.net/frobenius.pdf

[8] Brauer A. On a problem of partitions // Am. J. Math. 1942. Vol. 64. P. 299–312.

[9] Brauer A., Shockley J. E. On a problem of Frobenius // J. Reine Angew. Math. 1962. Vol. 211. P. 215–220.

[10] Curtis F. On formulas for the Frobenius number of a numerical semigroup // Math. Scand. 1990. Vol. 67. P. 190–192.

[11] Heap B. R., Lynn M. S. A graph-theoretic algorithm for the solution of a linear Diophantine problem of Frobenius // Numer. Math. 1964. Vol. 6. P. 346–354.

[12] Heap B. R., Lynn M. S. On a linear Diophantine problem of Frobenius: an improved algorithm // Numer. Math. 1965. Vol. 7. P. 226–231.

[13] Johnson D. B. Efficient algorithms for shortest paths in space networks // JACM. 1977. Vol. 24. P. 1–13.

[14] Nijenhuis M. A minimal-path algorithm for the “Money changing problem” // Am. Math. Mon. 1979. Vol. 86. P. 832–835.

[15] Ramírez Alfonsín J. L. The Diophantine Frobenius problem. Oxford: Clarendon Press, 2005. 243 p. (Oxf. Lect. Ser. Math. Appl.; Vol. 30).

[16] Sylvester J. J. Problem 7382 // Mathematical Questions with Their Solutions: From the “Educational Times”, London: Francis Hodgson, 1884. Vol. 41. P. 21.