|
|
| Строка 1: |
Строка 1: |
| − | [[3SAT]] или «3-Выполнимость» — частный случай задачи [[SAT]], в которой все дизъюнкции имеют не более чем три терма. | + | [[3SAT]] или «[[3-Выполнимость]]» — частный случай задачи [[SAT]], в которой все дизъюнкции имеют не более чем три терма. |
| | | | |
| | Однако, показано, что несмотря на это ограничение, [[3SAT]] является [[NPC|NP-полной]] задачей. | | Однако, показано, что несмотря на это ограничение, [[3SAT]] является [[NPC|NP-полной]] задачей. |
Версия 19:07, 19 апреля 2006
3SAT или «3-Выполнимость» — частный случай задачи SAT, в которой все дизъюнкции имеют не более чем три терма.
Однако, показано, что несмотря на это ограничение, 3SAT является NP-полной задачей.
