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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 8: Строка 8:
 
<latex>
 
<latex>
 
$$
 
$$
(x_1 \vee ... \vee x_k)(\overline{x_1}\vee ... \vee\overline{x_k})
+
(x_1)\wedge(\overline{x_1})\wedge(x_2)\wedge(\overline{x_2}) ... \wedge (x_k)\wedge(\overline{x_k})
 
$$
 
$$
 
</latex>
 
</latex>
Очевидно, что обе скобки выполнимы, но выполнена либо первая (все переменные равны единице), либо вторая (все переменные равны нулю), либо ни одна (другие случаи). Таким образом не выполнено более половины скобок (те обе) на любом наборе переменных
+
Очевидно, что выполнена только половина скобок.
  
 
[[Category:На проверку]]
 
[[Category:На проверку]]

Версия 11:04, 2 декабря 2014

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

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

Решение.

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