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

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

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

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

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