О сложности решения одного класса задач целочисленного линейного программирования

Рассматривается задача о рюкзаке, в которой множество допустимых значений $M$ вычисляется с использованием оракула, отвечающего на вопрос "$x\in M$?". Установлены нижние оценки числа обращений к оракулу. Предлагаемые оценки близки к известным верхним оценкам.
Библиогр. 13.