Изменения
Нет описания правки
:# Пусть в результате работы функции <tex>f</tex> получили выполнимую формулу <tex>\varphi</tex>, следовательно существует такой набор переменных <tex>Y_{i,j,c}</tex>, что <tex>\varphi</tex> на нем принимает значение ''истина''. Тогда по данному набору можем построить таблицу, по которой восстановим допускающую цепочку переходов <tex>q_0 \vdash q_1 \vdash ... \vdash q_t</tex>. Совершив эти переходы машина <tex>m</tex> перейдет в допускающее состояние за время <tex>t</tex>, следовательно <tex>\langle m, x, 1^t\rangle \in \mathrm{BH_{1N}}</tex>.
:Значит <tex> \mathrm{SAT} \in \mathrm{NPC} </tex>, что и требовалось доказать.
}}
== Другие примеры NP-полных языков ==
=== NP-полнота CNFSAT ===
<tex> \mathrm{CNFSAT} </tex>{{---}} язык булевых формул, заданных в [[КНФ]], таких что для них существует подстановка, при которой формула истинна.
<tex> \mathrm{CNFSAT} = \lbrace \varphi(x_1 \ldots x_n) \bigm| \varphi </tex> задано в КНФ и <tex> \exists x_1 \ldots x_n : \varphi(x_1 \ldots x_n) = 1 \rbrace </tex>
:Значит <tex> \mathrm{CNFSAT} \in \mathrm{NP} \land \mathrm{CNFSAT} \in \mathrm{NPH} \Rightarrow \mathrm{CNFSAT} \in \mathrm{NPC} </tex>.
}}
=== NP-полнота 3-SAT ===
* [[Классы NP и Σ₁]]
* [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
* [http://en.wikipedia.org/wiki/List_of_NP-complete_problems Список NP-полных задач]
[[Категория: Теория сложности]]
