MAX-SAT: вероятностное округление/Задачи/не более половины скобок — различия между версиями
Материал из DISCOPAL
Tsyganova (обсуждение | вклад) |
Tsyganova (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
<latex> | <latex> | ||
$$ | $$ | ||
| − | (x_1 | + | (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 переменных, построим КНФ следующим образом: Очевидно, что выполнена только половина скобок.