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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавил определение)
м (Банальный пример сведения по Карпу)
Строка 21: Строка 21:
 
* <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>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>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>IND \leq CLIQUE</tex>.<br>
+
{{Теорема
 +
|statement= <tex>IND \leq CLIQUE</tex>
 +
|proof=
 
Рассмотрим функцию <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>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 \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>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>IND \leq CLIQUE</tex> по определению.
 +
}}
 +
'''Замечание.''' Многие другие примеры сведения по Карпу могут быть найдены в статье про [[Примеры NP-полных языков. Теорема Кука | примеры NP-полных языков]].
  
'''Замечание.''' Многие другие примеры сведения по Карпу могут быть найдены в статье про [[Примеры NP-полных языков. Теорема Кука | примеры NP-полных языков]].
+
== Свойства сведения ==
  
 
{{Теорема
 
{{Теорема
Строка 36: Строка 40:
 
Проверим, что <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>|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>.
 
В итоге получаем, что итоговое время работы <tex>g(f(x))</tex> не более, чем <tex>p_2(p_1(|x|)) + p_1(|x|)</tex>, что является полиномом от <tex>|x|</tex>.
 +
}}
 +
 +
{{Лемма
 +
|statement=<tex>(L_1 \leq_{f} L_2) \Rightarrow (\overline {L_1} \leq_{f} \overline {L_2})</tex>
 +
|proof=Здесь пруф, ога.
 
}}
 
}}
  
Строка 50: Строка 59:
  
 
'''Замечание.''' Часто используется сведение по Карпу, поэтому слова «относительно сведения по Карпу» обычно опускаются. Например, [[Примеры NP-полных языков. Теорема Кука | NP-полные языки]].
 
'''Замечание.''' Часто используется сведение по Карпу, поэтому слова «относительно сведения по Карпу» обычно опускаются. Например, [[Примеры NP-полных языков. Теорема Кука | NP-полные языки]].
 
{{Лемма
 
|statement=<tex>(L_1 \leq_{f} L_2) \Rightarrow (\overline {L_1} \leq_{f} \overline {L_2})</tex>
 
|proof=Здесь пруф, ога.
 
}}
 

Версия 20:51, 8 мая 2012

Эта статья находится в разработке!

Определения

Определение:
[math]D[/math] — множество языков, [math]\widetilde{D}[/math]сведение — класс функций, соответствующих языкам из [math]D[/math].

Язык [math]L_1[/math] сводится к языку [math]L_2[/math] относительно [math]\widetilde{D}[/math] ([math]L_1 \leq_{\widetilde{D}} L_2[/math]), если существует такая функция [math]f(x)[/math] из [math]\widetilde{D}[/math], что [math]x[/math] принадлежит [math]L_1[/math] тогда и только тогда, когда [math]f(x)[/math] принадлежит [math]L_2[/math]:

[math] (L_1 \leq_{\widetilde{D}} L_2) \overset{\underset{\mathrm{def}}{}}{\Leftrightarrow} ( \exists f \in \widetilde{D} : x \in L_1 \Leftrightarrow f(x) \in L_2 ) [/math].


Теперь можно определить сведение по Карпу как частный случай сведения.


Определение:
Язык [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) \overset{\underset{\mathrm{def}}{}}{\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]\triangleright[/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] по определению.
[math]\triangleleft[/math]

Замечание. Многие другие примеры сведения по Карпу могут быть найдены в статье про примеры NP-полных языков.

Свойства сведения

Теорема (о транзитивности):
Сведение по Карпу транзитивно, то есть: [math] ( L_1 \leq L_2, L_2 \leq L_3 ) \Rightarrow L_1 \leq L_3 [/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]f[/math] и [math]g[/math] — функции из определения сведения для [math] L_1 \leq L_2 [/math] и [math] L_2 \leq L_3 [/math] соответственно. Из определения следует: [math]x \in L_1 \Leftrightarrow f(x) \in L_2 \Leftrightarrow g(f(x)) \in L_3[/math].
Проверим, что [math]g(f(x))[/math] вычислима за полиномиальное время от [math]|x|[/math]. В самом деле, сначала нужно вычислить [math]f(x)[/math], на это необходимо не более, чем [math]p_1(|x|)[/math] времени ([math]p_1[/math] — полином). Более того, длина входа [math]g[/math] в [math]g(f(x))[/math] не превышает того же [math]p_1(|x|)[/math], так как за единицу времени может быть выведен максимум один символ. Значит, вычисление [math]g[/math] на [math]f(x)[/math] займёт времени не более, чем [math]p_2(|f(x)|)[/math] ([math]p_2[/math] — тоже полином), что, по выше сказанному, не превосходит [math]p_2(p_1(|x|))[/math].

В итоге получаем, что итоговое время работы [math]g(f(x))[/math] не более, чем [math]p_2(p_1(|x|)) + p_1(|x|)[/math], что является полиномом от [math]|x|[/math].
[math]\triangleleft[/math]
Лемма:
[math](L_1 \leq_{f} L_2) \Rightarrow (\overline {L_1} \leq_{f} \overline {L_2})[/math]
Доказательство:
[math]\triangleright[/math]
Здесь пруф, ога.
[math]\triangleleft[/math]


Определение:
[math]C[/math] — сложностный класс, [math]\widetilde{D}[/math] — сведение. Язык [math]L[/math] называется [math]C[/math]-трудным относительно сведения [math]\widetilde{D}[/math] ([math]C[/math]-hard), если любой язык [math]M[/math] из [math]C[/math] сводится по [math]\widetilde{D}[/math] к [math]L[/math]:
[math] (L [/math][math]C[/math]-hard [math]) \overset{\underset{\mathrm{def}}{}}{\Leftrightarrow} ( \forall M \in C \Rightarrow M \leq_{f} L, f \in \widetilde{D} ) [/math].


Определение:
[math]C[/math] — сложностный класс, [math]\widetilde{D}[/math] — сведение. Язык [math]L[/math] называется [math]C[/math]-полным относительно сведения [math]\widetilde{D}[/math] ([math]C[/math]-complete), если [math]L[/math] является [math]C[/math]-трудным относительно сведения [math]\widetilde{D}[/math] и сам лежит в [math]C[/math].


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