Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/scheduling-ident-machines-in-npc — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: добавление Категория:Теоретические задачи)
 
Строка 5: Строка 5:
  
 
[[Категория:Нерешенные задачи]]
 
[[Категория:Нерешенные задачи]]
 +
[[Категория:Теоретические задачи]]

Текущая версия на 06:51, 4 мая 2023

Рассмотрим задачу разрешения для оптимизационной задачи Планирование Задач на Одинаковых Машинах («если ли планировка с максимальным временем меньше k»).

Покажите, что эта задача, даже в случае p=2, NP-полна.