MAX-SAT: вероятностное округление/Задачи/не более половины скобок — различия между версиями
Материал из DISCOPAL
Tsyganova (обсуждение | вклад) |
Tsyganova (обсуждение | вклад) |
||
| Строка 11: | Строка 11: | ||
$$ | $$ | ||
</latex> | </latex> | ||
| − | Очевидно, что обе скобки выполнимы, но выполнена либо первая (все переменные равны единице), либо вторая (все переменные равны нулю), либо ни одна (другие случаи) | + | Очевидно, что обе скобки выполнимы, но выполнена либо первая (все переменные равны единице), либо вторая (все переменные равны нулю), либо ни одна (другие случаи). Таким образом не выполнено более половины скобок (те обе) на любом наборе переменных |
[[Category:На проверку]] | [[Category:На проверку]] | ||
Версия 14:56, 30 ноября 2014
Цыганова Светлана, 974гр
Приведите пример задачи max-sat (невырожденный случай, т.е. КНФ для любого числа переменных, а не просто пустая формула), для которой на любом наборе переменных выполнено не более половины скобок
Решение.
Таких примеров много, приведу один простой. Пусть нам дано k переменных, построим КНФ следующим образом: Очевидно, что обе скобки выполнимы, но выполнена либо первая (все переменные равны единице), либо вторая (все переменные равны нулю), либо ни одна (другие случаи). Таким образом не выполнено более половины скобок (те обе) на любом наборе переменных