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