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

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

Версия 15:49, 20 мая 2020

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

  • А менее половины скобок?