2SAT

From Традиция
(Redirected from 2-Выполнимость)
Jump to navigation Jump to search

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

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