Архив публикаций

Тезисы

XVI-ая конференция

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

Урываев Б. В.

Ярославский государственный университет, Россия, 150000, г. Ярославль, ул. Советская 14, Е-mail: boreas@rambler.ru

Рассматривается задача распознавания целочисленности для класса многогранников, порождённых задачей о 3-выполнимости. Устанавливается, что задача распознавания целочисленности в этом классе NP-полна.

• открыть в PDF формате