1632
правки
Изменения
м
<tex>D</tex> — класс языков, удовлетворяющих некоторым ограничениям; <tex>\widetilde{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</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> называется '''сведением по Карпу'''.
'''Замечание.''' Часто используется именно сведение по Карпу, поэтому слова «относительно сведения по Карпу» и индекс у символа сведения обычно опускают.
== Определения трудных и сложных задач ==
rollbackEdits.php mass rollback
{{Определение
|definition =
}}
== Простой пример сведения по Карпу ==
|statement=Сведение по Карпу транзитивно, то есть: <tex> ( L_1 \leq L_2, L_2 \leq L_3 ) \Rightarrow L_1 \leq L_3 </tex>.
|proof=
Пусть <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</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>.
}}
== Определения трудных и полных задач ==
{{Определение
|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>-сводится по Карпу» говорят просто «сводится». Также индекс у символа сведения обычно опускают.
{{Лемма
|statement=<tex>(L_1 \leq_{\widetilde{D}} L_2) \Leftrightarrow (\overline {L_1} \leq_{\widetilde{D}} \overline {L_2})</tex>
|id=lemma
|proof=
По определению сведения существует такая функция <tex>f</tex> из класса <tex>\widetilde{D}</tex>, что <tex>x \in L_1 \Leftrightarrow f(x) \in L_2</tex>. Для того, чтобы свести <tex>\overline{L_1}</tex> к <tex>\overline{L_2}</tex> будем использовать ту же функцию <tex>f</tex>.<br>
В самом деле: <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>.
}}
{{Определение
|definition =
<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> (L </tex> — <tex>C</tex>-hard <tex>) \overset{\underset{\mathrm{def}}{}}{\Leftrightarrow} ( \forall M \in C \Rightarrow M \leq_{f} L, f \in \widetilde{D} ) </tex>.
}}
<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>.
}}
[[Категория: Теория сложности]]
