2SAT — различия между версиями
Материал из CustisWiki
BenderBot (обсуждение | вклад) м (реплицировано из внутренней CustisWiki) |
StasFomin (обсуждение | вклад) м |
||
Строка 1: | Строка 1: | ||
− | [[2SAT]] или | + | [[2SAT]] или «[[2-Выполнимость]]» — частный случай задачи [[SAT]], в которой все дизъюнкции имеют не более чем два терма. |
Эта задача полиномиально разрешима (т.е. лежит в классе [[P]]) алгоритмом [[2SAT:Решение]]. | Эта задача полиномиально разрешима (т.е. лежит в классе [[P]]) алгоритмом [[2SAT:Решение]]. |
Версия 19:06, 19 апреля 2006
2SAT или «2-Выполнимость» — частный случай задачи SAT, в которой все дизъюнкции имеют не более чем два терма.
Эта задача полиномиально разрешима (т.е. лежит в классе P) алгоритмом 2SAT:Решение.
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».
Репликация: База Знаний «Заказных Информ Систем» → «2SAT»