|
Архив публикацийТезисыXVI-ая конференцияО задаче распознавания целочисленности для одного класса многогранниковЯрославский государственный университет, Россия, 150000, г. Ярославль, ул. Советская 14, Е-mail: boreas@rambler.ru 1 стр. (принято к публикации)Рассматривается задача распознавания целочисленности для класса многогранников, порождённых задачей о 3-выполнимости. Устанавливается, что задача распознавания целочисленности в этом классе NP-полна. |