SAT

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

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

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

, , и .

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

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

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

---

Внимание! Данная статья выбрана для репликации во внешнюю базу знаний компании. Пожалуйста, не допускайте в этой статье публикацию конфиденциальной информации, ведения обсуждений в теле статьи, и более ответственно относитесь к качеству самой статьи — проверяйте орфографию, пишите по-русски, избегайте непроверенной вами информации.