https://discopal.ispras.ru/index.php?action=history&feed=atom&title=SATSAT - История изменений2026-04-14T11:39:40ZИстория изменений этой страницы в викиMediaWiki 1.26.4https://discopal.ispras.ru/index.php?title=SAT&diff=842&oldid=prevWikiSysop: 1 версия2008-08-04T09:55:49Z<p>1 версия</p>
<p><b>Новая страница</b></p><div>[[SAT]], от ''Satisfiability'', в русскоязычной литературе — «[[Выполнимость]]».<br />
Формулировка задачи:<br />
<br />
Дано булевское выражение, являющееся ''коньюнктивной нормальной формой'' (КНФ):<br />
<br />
<amsmath><br />
\bigwedge_{i=1}^m K_i,<br />
</amsmath><br />
<br />
где ''K<sub>i</sub>'' — ''элементарные дизьюнкции'' вида<br />
<br />
<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>.<br />
<br />
Существует ли (булевский) набор переменных ''x<sub>j</sub>'', обращающий эту форму в «1» (т. е. в «TRUE»)?<br />
<br />
Известно, что задача [[SAT]] — [[NPC|NP-полна]].<br />
<br />
Известные частные случаи — задачи [[3SAT]] и [[2SAT]].<br />
<br />
<br />
[[Category:Задачи]]<br />
{{replicate-from-custiswiki-to-lib}}</div>WikiSysop