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