|
|
| Строка 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}}
| + | |
