Проблема Фробениуса для классов полиномиальной разрешимости

Проблема Фробениуса состоит в нахождении способа ($=$ алгоритма) вычисления наибольшей “суммы денег”, которую нельзя выдать монетами, имеющими взаимно простые достоинства $b_0,b_1,\dots,b_w$. В качестве приемлемых (алгоритмов) решений принято рассматривать полиномиальные, названные так по форме зависимости затрат времени от длины исходной информации. О трудности проблемы Фробениуса говорит тот факт, что вопрос о существовании полиномиального решения уже для $w=3$ остается открытым. В настоящей статье выделяются некоторые классы аргументов, на которых проблема решается полиномиально; между тем, рассуждения в духе теории сложности алгоритмов сведены к минимуму.
Библиография: 9 названий.