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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Определения трудных и сложных задач: о_0 !!!!!!)
Строка 2: Строка 2:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
<tex>D</tex> — класс языков, распознаваемых программами с некоторыми ограничениями. Тогда обозначим <tex>\widetilde{D}</tex> класс вычислимых функций, вычисляемых программами с теми же ограничениями.
+
'''Язык <tex>L_1</tex> сводится по Карпу к языку <tex>L_2</tex> (<tex>L_1 \leq L_2</tex>)''', если существует такая функция <tex>f</tex>, работающая за полином, что <tex>x</tex> принадлежит <tex>L_1</tex> тогда и только тогда, когда <tex>f(x)</tex> принадлежит <tex>L_2</tex>.
}}
 
{{Определение
 
|definition =
 
'''Язык <tex>L_1</tex> <tex>\widetilde{D}</tex>-сводится по Карпу к языку <tex>L_2</tex> (<tex>L_1 \leq_{\widetilde{D}} L_2</tex>)''', если существует такая функция <tex>f</tex> из <tex>\widetilde{D}</tex>, что <tex>x</tex> принадлежит <tex>L_1</tex> тогда и только тогда, когда <tex>f(x)</tex> принадлежит <tex>L_2</tex>:<br>
 
<tex> (L_1 \leq_{\widetilde{D}} L_2) \overset{\underset{\mathrm{def}}{}}{\iff} ( \exists f \in \widetilde{D} : x \in L_1 \Leftrightarrow f(x) \in L_2 ) </tex>.
 
 
}}
 
}}
'''Замечание.''' Часто используется сведение из <tex>\widetilde{P}</tex>, поэтому вместо «<tex>\widetilde{P}</tex>-сводится по Карпу» говорят просто «сводится». Также индекс у символа сведения обычно опускают.
 
  
 
== Простой пример сведения по Карпу ==
 
== Простой пример сведения по Карпу ==
Строка 39: Строка 33:
 
Таким образом, полное время работы программы есть сумма полиномов от <tex>|x|</tex> и потому тоже является полиномом от <tex>|x|</tex>.
 
Таким образом, полное время работы программы есть сумма полиномов от <tex>|x|</tex> и потому тоже является полиномом от <tex>|x|</tex>.
 
}}
 
}}
 +
 +
== Определения трудных и полных задач ==
 +
 +
{{Определение
 +
|definition =
 +
<tex>C</tex> — сложностный класс. Язык <tex>L</tex> называется '''<tex>C</tex>-трудным (относительно полиномиального сведения) (<tex>C</tex>-hard)''', если любой язык <tex>M</tex> из <tex>C</tex> сводится по Карпу к <tex>L</tex>:<br>
 +
<tex> (L </tex> — <tex>C</tex>-hard <tex>) \overset{\underset{\mathrm{def}}{}}{\Leftrightarrow} ( \forall M \in C \Rightarrow M \leq L) </tex>.
 +
}}
 +
 +
{{Определение
 +
|definition =
 +
<tex>C</tex> — сложностный класс. Язык <tex>L</tex> называется '''<tex>C</tex>-полным (относительно полиномиального сведения) (<tex>C</tex>-complete)''', если <tex>L</tex> является <tex>C</tex>-трудным и сам лежит в <tex>C</tex>.
 +
}}
 +
 +
== Обобщение на другие ограничения на сведения ==
 +
{{Определение
 +
|definition =
 +
<tex>D</tex> — класс языков, распознаваемых программами с некоторыми ограничениями. Тогда обозначим <tex>\widetilde{D}</tex> класс вычислимых функций, вычисляемых программами с теми же ограничениями.
 +
}}
 +
{{Определение
 +
|definition =
 +
'''Язык <tex>L_1</tex> <tex>\widetilde{D}</tex>-сводится по Карпу к языку <tex>L_2</tex> (<tex>L_1 \leq_{\widetilde{D}} L_2</tex>)''', если существует такая функция <tex>f</tex> из <tex>\widetilde{D}</tex>, что <tex>x</tex> принадлежит <tex>L_1</tex> тогда и только тогда, когда <tex>f(x)</tex> принадлежит <tex>L_2</tex>:<br>
 +
<tex> (L_1 \leq_{\widetilde{D}} L_2) \overset{\underset{\mathrm{def}}{}}{\iff} ( \exists f \in \widetilde{D} : x \in L_1 \Leftrightarrow f(x) \in L_2 ) </tex>.
 +
}}
 +
'''Замечание.''' Часто используется сведение из <tex>\widetilde{P}</tex>, поэтому вместо «<tex>\widetilde{P}</tex>-сводится по Карпу» говорят просто «сводится». Также индекс у символа сведения обычно опускают.
  
 
{{Лемма
 
{{Лемма
Строка 47: Строка 66:
 
В самом деле: <tex>( x \in L_1 \Leftrightarrow f(x) \in L_2 ) \iff ( \overline{x \in L_1} \Leftrightarrow \overline{f(x) \in L_2} ) </tex> <tex>\iff ( x \in \overline{L_1} \Leftrightarrow f(x) \in \overline{L_2} ) \iff (\overline {L_1} \leq_{\widetilde{D}} \overline {L_2})</tex>.
 
В самом деле: <tex>( x \in L_1 \Leftrightarrow f(x) \in L_2 ) \iff ( \overline{x \in L_1} \Leftrightarrow \overline{f(x) \in L_2} ) </tex> <tex>\iff ( x \in \overline{L_1} \Leftrightarrow f(x) \in \overline{L_2} ) \iff (\overline {L_1} \leq_{\widetilde{D}} \overline {L_2})</tex>.
 
}}
 
}}
 
== Определения трудных и полных задач ==
 
  
 
{{Определение
 
{{Определение

Версия 17:54, 1 июня 2018

Определения

Определение:
Язык [math]L_1[/math] сводится по Карпу к языку [math]L_2[/math] ([math]L_1 \leq L_2[/math]), если существует такая функция [math]f[/math], работающая за полином, что [math]x[/math] принадлежит [math]L_1[/math] тогда и только тогда, когда [math]f(x)[/math] принадлежит [math]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]|x|[/math] времени.
Кроме того, длина входа [math]g[/math], являющегося выводом [math]f(x)[/math], тоже полиномиальна, так как за единицу времени может быть выведено не более, чем константное число символов. Значит, вычисление [math]g(f(x))[/math] также займет времени не более, чем полином от [math]|x|[/math].

Таким образом, полное время работы программы есть сумма полиномов от [math]|x|[/math] и потому тоже является полиномом от [math]|x|[/math].
[math]\triangleleft[/math]

Определения трудных и полных задач

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


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


Обобщение на другие ограничения на сведения

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


Определение:
Язык [math]L_1[/math] [math]\widetilde{D}[/math]-сводится по Карпу к языку [math]L_2[/math] ([math]L_1 \leq_{\widetilde{D}} L_2[/math]), если существует такая функция [math]f[/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}}{}}{\iff} ( \exists f \in \widetilde{D} : x \in L_1 \Leftrightarrow f(x) \in L_2 ) [/math].

Замечание. Часто используется сведение из [math]\widetilde{P}[/math], поэтому вместо «[math]\widetilde{P}[/math]-сводится по Карпу» говорят просто «сводится». Также индекс у символа сведения обычно опускают.

Лемма:
[math](L_1 \leq_{\widetilde{D}} L_2) \Leftrightarrow (\overline {L_1} \leq_{\widetilde{D}} \overline {L_2})[/math]
Доказательство:
[math]\triangleright[/math]

По определению сведения существует такая функция [math]f[/math] из класса [math]\widetilde{D}[/math], что [math]x \in L_1 \Leftrightarrow f(x) \in L_2[/math]. Для того, чтобы свести [math]\overline{L_1}[/math] к [math]\overline{L_2}[/math] будем использовать ту же функцию [math]f[/math].

В самом деле: [math]( x \in L_1 \Leftrightarrow f(x) \in L_2 ) \iff ( \overline{x \in L_1} \Leftrightarrow \overline{f(x) \in L_2} ) [/math] [math]\iff ( x \in \overline{L_1} \Leftrightarrow f(x) \in \overline{L_2} ) \iff (\overline {L_1} \leq_{\widetilde{D}} \overline {L_2})[/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].