38
правок
Изменения
Нет описания правки
== NP-полнота <tex> SAT </tex> ==
<tex> SAT </tex> {{---}} язык булевых формулиз <tex> n </tex> переменных, для которых существует подстановка, при которой формула истинна.
<tex> SAT = \lbrace \varphi\ |\ \exists x : \varphi(x) = 1 \rbrace </tex>
|proof=
# <tex> SAT \in NPH </tex>
# <tex> SAT \in NP </tex> <br>Можно написать недетерминированную программу<tex> p</tex>, которая распознает язык <tex> SAT</tex>. Она будет недетерминированно выбирать подстановку, проверять истинна ли формула при такой подстановке и выдавать ответ.:<font size = 2> <tex>p(\varphi)</tex> for <tex> i \in \lbrace 1 \ldots n \rbrace </tex>: <tex> x_i </tex> = random(2); if <tex> \varphi(x) </tex> == 1: return 1 else return 0</font>
}}
== Другие примеры NP-полных языков ==
=== NP-полнота 3-SAT ===
=== NP-полнота раскраски графа ===
=== NP-полнота поиска минимального вершинного покрытия в графе ===
=== NP-полнота поиска максимальной клики в графе ===
=== NP-полнота поиска гамильтонова цикла и пути в графе ===
=== NP-полнота задачи о рюкзаке ===
[[Категория: Теория сложности]]
