MAX-SAT: вероятностное округление/Задачи/не более половины скобок — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена Решенные задачи]] на Нерешенные задачи) |
StasFomin (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
* А менее половины скобок? | * А менее половины скобок? | ||
| − | [[Категория:Нерешенные задачи | + | [[Категория:Нерешенные задачи]] |
Версия 10:02, 18 декабря 2017
Приведите пример задачи max-sat (невырожденный случай, т.е. КНФ для любого числа переменных, а не просто пустая формула), для которой на любом наборе переменных выполнено не более половины скобок.
- А менее половины скобок?