Изменения

Пусть <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>|x|</tex> времени. Более <br/>Кроме того, длина входа <tex>g</tex> в , являющегося выводом <tex>g(f(x))</tex> , тоже полиномиальна, так как за единицу времени может быть выведено не более, чем константное число символов. Значит, вычисление <tex>g</tex> на <tex>(f(x))</tex> займёт также займет времени не более, чем полиномот <tex>|x|</tex>.В итоге получаемТаким образом, что итоговое полное время работы программы есть сумма полиномов от <tex>g(f(|x))|</tex> полиномиально и потому тоже является полиномом от <tex>|x|</tex>.