Изменения

<tex>D</tex> — множество языков, <tex>\widetilde{D}</tex> — класс функций, соответствующих языкам из <tex>D</tex>.'''Язык <tex>L_1</tex> сводится по Карпу к языку <tex>L_2</tex> относительно <tex>\widetilde{D}</tex> (<tex>L_1 \leq_{\widetilde{D}} leq L_2</tex>)''', если существует такая функция <tex>f(x)</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>.}}{{Определение|definition =Сведение относительно <tex>\widetilde{P}</tex> называется '''сведением по Карпу'''.

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

* <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>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>.

'''Замечание.''' Многие другие Другие примеры сведения по Карпу могут быть найдены приведены в статье про , содержащей [[Примеры NP-полных языков. Теорема Кука | примеры NP-полных языков]].

Пусть <tex>f</tex> и <tex>g</tex> — функции из определения сведения для <tex> L_1 \leq L_2 </tex> и <tex> L_2 \leq L_3 </tex> соответственно. Из определения следует: <tex>x \in L_1 \Leftrightarrow f(x) \in L_2 \Leftrightarrow g(f(x)) \in L_3</tex>.<br> Проверим, что <tex>g(f(x))</tex> вычислима за полиномиальное время от <tex>|x|</tex>время. В самом деле<br/>Действительно, сначала нужно первым делом необходимо вычислить <tex>f(x)</tex>, на это необходимо не более, чем уйдет полином от <tex>p_1(|x|)</tex> времени (<tex>p_1.<br/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|x|</tex> — и потому тоже полином), что, по выше сказанному, не превосходит является полиномом от <tex>p_2(p_1(|x|))</tex>.В итоге получаем, что итоговое время работы }} == Определения трудных и полных задач == {{Определение|definition =<tex>C</tex> — сложностный класс. Язык <tex>L</tex> называется '''<tex>C</tex>g-трудным (fотносительно полиномиального сведения) (x)<tex>C</tex>-hard)''', если любой язык <tex>M</tex> из <tex>C</tex> сводится по Карпу к <tex>L</tex> не более, чем :<br><tex>p_2(p_1L </tex> — <tex>C</tex>-hard <tex>) \overset{\underset{\mathrm{def}}{}}{\Leftrightarrow} (\forall M \in C \Rightarrow M \leq L) </tex>.}} {{Определение|x|)definition =<tex>C</tex> — сложностный класс. Язык <tex>L</tex> называется '''<tex>C</tex>-полным (относительно полиномиального сведения) + p_1(|x|<tex>C</tex>-complete)''', если <tex>L</tex>, что является полиномом от <tex>|x|C</tex>-трудным и сам лежит в <tex>C</tex>.

<tex>C</tex> — сложностный класс, <tex>\widetilde{D}</tex> — сведениекласс вычислимых функций. Язык <tex>L</tex> называется '''<tex>C</tex>-трудным относительно <tex>\widetilde{D}</tex>-сведения (<tex>C</tex>-hard)''', если любой язык <tex>M</tex> из <tex>C</tex> сводится к <tex>L\widetilde{D}</tex> относительно -сводится к <tex>\widetilde{D}L</tex>:<br>

<tex>C</tex> — сложностный класс, <tex>\widetilde{D}</tex> — сведениекласс вычислимых функций. Язык <tex>L</tex> называется '''<tex>C</tex>-полным относительно <tex>\widetilde{D}</tex>-сведения (<tex>C</tex>-complete)''', если <tex>L</tex> является <tex>C</tex>-трудным относительно <tex>\widetilde{D}</tex>-сведения и сам лежит в <tex>C</tex>.