editor
177
правок
Изменения
Добавил определение сложного языка
Проверим, что <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>.
}}
{{Определение
|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>\widetilde{D}</tex> к <tex>L</tex>:<br>
<tex> (L </tex> — <tex>C</tex>-hard <tex>) \Leftrightarrow ( \forall M \in C \Rightarrow M \leq_{f} L, f \in \widetilde{D} ) </tex>.
}}
