MAX-SAT: вероятностное округление/Задачи/не более половины скобок — различия между версиями

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

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

Приведите пример задачи max-sat (невырожденный случай, т.е. КНФ для любого числа переменных, а не просто пустая формула), для которой на любом наборе переменных выполнено не более половины скобок.

  • А менее половины скобок?