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