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