Изменения

* <tex>IND</tex> — множество пар вида <tex> \langle G, k \rangle </tex>, где <tex>G</tex> — граф, а <tex>k</tex> — число, таких, что в <tex>G</tex> есть [http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B5%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D0%BE%D0%BC_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B5#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F независимое множество] размера <tex>k</tex>.

* <tex>CLIQUE</tex> — множество пар вида <tex> \langle G, k \rangle </tex>, где <tex>G</tex> — граф, а <tex>k</tex> — число, такое, что в <tex>G</tex> есть [http://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B8%D0%BA%D0%B0_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2) клика] размера <tex>k</tex>.

Рассмотрим функцию <tex>f( \langle G, k \rangle ) = \langle \overline{G}, k \rangle</tex>, где <tex>\overline{G}</tex> — [http://ru.wikipedia.org/wiki/%D0%94%D0%BE%D0%BF%D0%BE%D0%BB%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B3%D1%80%D0%B0%D1%84%D0%B0 дополнение графа] <tex>G</tex>. <tex>f</tex> вычислима за линейное время от длины входа, если граф представлен в видел матрицы смежности.<br>

* (<tex>x \in L_1 \Rightarrow f(x) \in L_2</tex>) Заметим, что, если в <tex>G</tex> было независимое множество размера <tex>k</tex>, то в <tex>\overline{G}</tex> будет клика такого же размера (вершины, которые были в независимом множестве, в <tex>\overline{G}</tex> попарно соединены рёбрами и образуют клику).

* (<tex>x \in L_1 \Leftarrow f(x) \in L_2</tex>) Обратно, если в <tex>\overline{G}</tex> есть клика размера <tex>k</tex>, то в исходном графе было независимое множество размера <tex>k</tex>.

Таким образом, <tex>IND \leq CLIQUE</tex> по определению.

{{Теорема

Проверим, что <tex>g(f(x))</tex> вычислима за полиномиальное время от <tex>|x|</tex>. В самом деле, сначала нужно вычислить <tex>f(x)</tex>, на это необходимо не более, чем <tex>p_1(|x|)</tex> времени (<tex>p_1</tex> — полином). Более того, длина входа <tex>g</tex> в <tex>g(f(x))</tex> не превышает того же <tex>p_1(|x|)</tex>, так как за единицу времени может быть выведен максимум один символ. Значит, вычисление <tex>g</tex> на <tex>f(x)</tex> займёт времени не более, чем <tex>p_2(|f(x)|)</tex> (<tex>p_2</tex> — тоже полином), что, по выше сказанному, не превосходит <tex>p_2(p_1(|x|))</tex>.

В итоге получаем, что итоговое время работы <tex>g(f(x))</tex> не более, чем <tex>p_2(p_1(|x|)) + p_1(|x|)</tex>, что является полиномом от <tex>|x|</tex>.

}}

'''Замечание.''' Часто используется сведение по Карпу, поэтому слова «относительно сведения по Карпу» обычно опускаются. Например, [[Примеры NP-полных языков. Теорема Кука | NP-полные языки]].