Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи

Материал из Викиконспекты
Версия от 21:24, 15 апреля 2012; Leugenea (обсуждение | вклад) (Добавил пример сведения)
Перейти к: навигация, поиск
Эта статья находится в разработке!


Определение:
Язык [math]L_1[/math] сводится по Карпу к языку [math]L_2[/math] ([math]L_1 \leq L_2[/math]), если существует такая функция [math]f(x)[/math], вычислимая за полиномиальное от длины входа время, что [math]x[/math] принадлежит [math]L_1[/math] тогда и только тогда, когда [math]f(x)[/math] принадлежит [math]L_2[/math]:
[math] (L_1 \leq L_2) \Leftrightarrow ( \exists f \in P : x \in L_1 \Leftrightarrow f(x) \in L_2 ) [/math].


Банальный пример сведения по Карпу

Зададим следующие языки:

  • [math]IND[/math] — множество пар вида [math] \langle G, k \rangle [/math], где [math]G[/math] — граф, а [math]k[/math] — число, таких, что в [math]G[/math] есть независимое множество размера [math]k[/math].
  • [math]CLIQUE[/math] — множество пар вида [math] \langle G, k \rangle [/math], где [math]G[/math] — граф, а [math]k[/math] — опять же, число, таких, что в [math]G[/math] есть клика размера [math]k[/math].

Докажем, что [math]IND \leq CLIQUE[/math].
Рассмотрим функцию [math]f( \langle G, k \rangle ) = \langle \overline{G}, k \rangle[/math], где [math]\overline{G}[/math]дополнение графа [math]G[/math]. [math]f[/math] вычислима за линейное время от длины входа, если граф представлен в видел матрицы смежности.

  • ([math]x \in L_1 \Rightarrow f(x) \in L_2[/math]) Заметим, что если в [math]G[/math] было независимое множество размера [math]k[/math], то в [math]\overline{G}[/math] будет клика такого же размера (вершины, которые были в независимом множестве, в [math]\overline{G}[/math] попарно соединены рёбрами и образуют клику).
  • ([math]x \in L_1 \Leftarrow f(x) \in L_2[/math]) Обратно, если в [math]\overline{G}[/math] есть клика размера [math]k[/math], то в исходном графе было независимое множество размера [math]k[/math].

Таким образом, [math]IND \leq CLIQUE[/math] по определению.