PCP и аппроксимируемость/Задачи/ex-max2sat-in-npc — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
м (StasFomin переименовал страницу Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-max2sat-in-npc в [[PCP и аппроксимируемость/Зад…)
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
Строка 8: Строка 8:
 
<!--Вообще-то, решения уже есть-->
 
<!--Вообще-то, решения уже есть-->
  
[[Категория:Нерешенные задачи]]
+
[[Категория:Решенные задачи]]

Версия 15:49, 20 мая 2020

Рассмотрим максимизационную версию задачи 2SAT, где дополнительно к 2SAT-формуле задается параметр K, и спрашивается, можно ли выполнить больше чем K, количество скобок.

Покажите, что эта задача NP-полна.