|
 |
Персональные инструменты
Просмотры |
|
Персональные инструменты |
|
||
|
|
SAT — различия между версиямиМатериал из CustisWiki
Версия 12:55, 4 августа 2008SAT, от Satisfiability, в русскоязычной литературе — «Выполнимость». Формулировка задачи: Дано булевское выражение, являющееся коньюнктивной нормальной формой (КНФ):
где Ki — элементарные дизьюнкции вида , , и . Существует ли (булевский) набор переменных xj, обращающий эту форму в «1» (т. е. в «TRUE»)? Известно, что задача SAT — NP-полна. Известные частные случаи — задачи 3SAT и 2SAT.
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». Репликация: База Знаний «Заказных Информ Систем» → «SAT» |
 |
||||
 |
||||||
 |
