|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Проблема Фробениуса для классов полиномиальной разрешимости
И. Д. Кан Московский государственный университет им. М. В. Ломоносова
Аннотация:
Проблема Фробениуса состоит в нахождении способа ($=$ алгоритма) вычисления наибольшей “суммы денег”, которую нельзя выдать монетами, имеющими взаимно простые
достоинства $b_0,b_1,\dots,b_w$. В качестве приемлемых (алгоритмов) решений
принято рассматривать полиномиальные, названные так по форме зависимости затрат времени от длины исходной информации. О трудности проблемы Фробениуса говорит тот
факт, что вопрос о существовании полиномиального решения уже для $w=3$ остается открытым. В настоящей статье выделяются некоторые классы аргументов, на которых
проблема решается полиномиально; между тем, рассуждения в духе теории сложности алгоритмов сведены к минимуму.
Библиография: 9 названий.
Поступило: 20.03.2000 Исправленный вариант: 25.12.2000
Образец цитирования:
И. Д. Кан, “Проблема Фробениуса для классов полиномиальной разрешимости”, Матем. заметки, 70:6 (2001), 845–853; Math. Notes, 70:6 (2001), 771–778
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mzm797https://doi.org/10.4213/mzm797 https://www.mathnet.ru/rus/mzm/v70/i6/p845
|
Статистика просмотров: |
Страница аннотации: | 474 | PDF полного текста: | 246 | Список литературы: | 60 | Первая страница: | 1 |
|