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