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

Версия 20:25, 20 декабря 2012

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