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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показано 20 промежуточных версий 2 участников)
Строка 1: Строка 1:
−
<big>Цыганова Светлана, 974гр</big>
+
Приведите пример задачи max-sat (невырожденный случай, т.е. КНФ для любого числа переменных, а не просто пустая формула), для которой на любом наборе переменных выполнено не более половины скобок.
  
−
Приведите пример задачи max-sat (невырожденный случай, т.е. КНФ для любого числа переменных, а не просто пустая формула), для которой на любом наборе переменных выполнено не более половины скобок
+
* А менее половины скобок?
  
−
'''Решение.'''
+
[[Категория:Решенные задачи]]
−
 
+
[[Категория:Теоретические задачи]]
−
Таких примеров много, приведу один простой. Пусть нам дано k переменных, построим КНФ следующим образом:
+
−
<latex>
+
−
$$
+
−
(x_1 \vee ... \vee x_k)(\overline{x_1}\vee ... \vee\overline{x_k})
+
−
$$
+
−
</latex>
+
−
Очевидно, что обе скобки выполнимы, но выполнена либо первая (все переменные равны единице), либо вторая (все переменные равны нулю), либо ни одна (другие случаи). Таким образом не выполнено более половины скобок (те обе) на любом наборе переменных
+
−
 
+
−
[[Category:На проверку]]
+

Текущая версия на 06:50, 4 мая 2023

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

  • А менее половины скобок?
Источник — «https://discopal.ispras.ru/index.php?title=MAX-SAT:_вероятностное_округление/Задачи/не_более_половины_скобок&oldid=25716»