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

Ссылки сюда (9) →

Цыганова Светлана, 974гр

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

Решение.

Таких примеров много, приведу один простой. Пусть нам дано k переменных, построим КНФ следующим образом: Очевидно, что обе скобки выполнимы, но выполнена либо первая (все переменные равны единице), либо вторая (все переменные равны нулю), либо ни одна (другие случаи)

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.