Персональные инструменты
 

SAT — различия между версиями

Материал из CustisWiki

Перейти к: навигация, поиск
м (1 версия)
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
Строка 1: Строка 1:
[[SAT]], от ''Satisfiability'', в русскоязычной литературе — «[[Выполнимость]]».
+
#REDIRECT [[discopal:{{PAGENAME}}]]
Формулировка задачи:
+
 
+
Дано булевское выражение, являющееся ''коньюнктивной нормальной формой'' (КНФ):
+
 
+
<amsmath>
+
    \bigwedge_{i=1}^m K_i,
+
</amsmath>
+
 
+
где ''K<sub>i</sub>'' — ''элементарные дизьюнкции'' вида
+
 
+
<amsmath>x_{j_1}^{\sigma_1}\lor\ldots\lor x_{j_k}^{\sigma_k}</amsmath>, <amsmath>\sigma_j\in\{0,1\}</amsmath>, <amsmath>x^1=x</amsmath> и <amsmath>x^0=(\neg x)</amsmath>.
+
 
+
Существует ли (булевский) набор переменных ''x<sub>j</sub>'', обращающий эту форму в «1» (т. е. в «TRUE»)?
+
 
+
Известно, что задача [[SAT]] — [[NPC|NP-полна]].
+
 
+
Известные частные случаи — задачи [[3SAT]] и [[2SAT]].
+
 
+
 
+
[[Category:Задачи]]
+
{{replicate-from-custiswiki-to-lib}}
+

Текущая версия на 20:26, 13 июня 2011

  1. REDIRECT discopal:SAT