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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 11: Строка 11:
 
$$
 
$$
 
</latex>
 
</latex>
Очевидно, что обе скобки выполнимы, но выполнена либо первая (все переменные равны единице), либо вторая (все переменные равны нулю), либо ни одна (другие случаи)
+
Очевидно, что обе скобки выполнимы, но выполнена либо первая (все переменные равны единице), либо вторая (все переменные равны нулю), либо ни одна (другие случаи). Таким образом не выполнено более половины скобок (те обе) на любом наборе переменных
  
 
[[Category:На проверку]]
 
[[Category:На проверку]]

Версия 14:56, 30 ноября 2014

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

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

Решение.

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