2SAT

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

2SAT или «2-Выполнимость» — частный случай задачи SAT, в которой все дизъюнкции имеют не более чем два терма.

Эта задача полиномиально разрешима (т.е. лежит в классе P) алгоритмом 2SAT:Решение.
По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.