SAT

Материал из DISCOPAL
Перейти к: навигация, поиск

SAT, от Satisfiability, в русскоязычной литературе — «Выполнимость». Формулировка задачи:

Дано булевское выражение, являющееся коньюнктивной нормальной формой (КНФ):

где Kiэлементарные дизьюнкции вида

, , и .

Существует ли (булевский) набор переменных xj, обращающий эту форму в «1» (т. е. в «TRUE»)?

Известно, что задача SATNP-полна.

Известные частные случаи — задачи 3SAT и 2SAT.