editor
177
правок
Изменения
Добавил теорему о транзитивности
* (<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> по определению.
'''Замечание.''' Многие другие примеры сведения по Карпу могут быть найдены в статье про [[Примеры NP-полных языков. Теорема Кука | примеры NP-полных языков]].
{{Теорема
|about=о транзитивности
|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>.
Проверим, что <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(p_1(|x|))</tex>.
В итоге получаем, что итоговое время работы <tex>g(f(x))</tex> не более, чем <tex>p_2(p_1(|x|)) + p_1(|x|)</tex>.
}}
