|
|
Строка 1: |
Строка 1: |
− | [[2SAT]] или «2-Выполнимость» — частный случай задачи [[SAT]], в которой все дизъюнкции имеют не более чем два терма. | + | [[2SAT]] или «[[2-Выполнимость]]» — частный случай задачи [[SAT]], в которой все дизъюнкции имеют не более чем два терма. |
| | | |
| Эта задача полиномиально разрешима (т.е. лежит в классе [[P]]) алгоритмом [[2SAT:Решение]]. | | Эта задача полиномиально разрешима (т.е. лежит в классе [[P]]) алгоритмом [[2SAT:Решение]]. |
Версия 19:06, 19 апреля 2006
2SAT или «2-Выполнимость» — частный случай задачи SAT, в которой все дизъюнкции имеют не более чем два терма.
Эта задача полиномиально разрешима (т.е. лежит в классе P) алгоритмом 2SAT:Решение.