NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ — различия между версиями
(Новая страница: «'''Теорема''' 3<tex>-SAT \in NPC </tex> (задача о выполнимости булевой формулы в форме 3-КНФ <tex>NP</tex>-полн…») |
|||
| Строка 1: | Строка 1: | ||
| − | '''Теорема''' | + | '''Теорема''' <tex>3SAT \in NPC </tex>, ''т.е. задача о выполнимости булевой формулы в форме 3-КНФ <tex>NP</tex>-полна.'' |
| + | '''Доказательство''' | ||
| + | Для того, чтобы доказать <tex>NP</tex>-полноту задачи, необходимо установить следующие факты: | ||
| + | # <tex> 3SAT \in NPH </tex>; | ||
| + | # <tex> 3SAT \in NP </tex>. | ||
Версия 23:02, 15 марта 2010
Теорема , т.е. задача о выполнимости булевой формулы в форме 3-КНФ -полна. Доказательство Для того, чтобы доказать -полноту задачи, необходимо установить следующие факты:
- ;
- .
