Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-equiv-in-3knf — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показано 13 промежуточных версий 2 участников)
Строка 1: Строка 1:
−
<big>Цыганова Светлана, 974гр.</big>
 
−
 
 
Выразите логическое отношение эквивалентности в виде 3-КНФ формулы.
 
Выразите логическое отношение эквивалентности в виде 3-КНФ формулы.
  
−
<latex>
 
−
\textbf{Решение}
 
  
−
Отношение эквивалентности $A \Leftrightarrow B$ записывается следующей 3-КНФ формулой: $(\overline{A}\vee B)\wedge(A\vee\overline{B})$
 
−
</latex>
 
  
−
[[Category:На проверку]]
+
<!--Вообще-то, решения уже есть-->
 +
 
 +
[[Категория:Решенные задачи]]

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

Выразите логическое отношение эквивалентности в виде 3-КНФ формулы.

Источник — «https://discopal.ispras.ru/index.php?title=Полиномиальные_сводимости_и_NP-полные_задачи._Классы_NP,_coNP,_NPC/Задачи/ex-equiv-in-3knf&oldid=11095»