Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/USUBSETSUM-IN-P

Материал из DISCOPAL
< Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC‎ | Задачи
Версия от 23:56, 3 марта 2021; StasFomin (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Вспомним задачу булев-рюкзак выполнимость, и потребуем, чтобы все веса и размер рюкзака задавались в унарной системе ().

Покажите, что тогда язык таких выполнимых рюкзаков, лежит в классе P.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.