51
правка
Изменения
→Доказательство транзитивности
Рассмотрим функция <tex>h(x) = g(f(x))</tex>. <tex>x \in A \Leftrightarrow f(x) \in B</tex>. Также <tex>f(x) \in B \Leftrightarrow g(f(x)) \in C</tex>. Т.е. <tex>x \in A \Leftrightarrow h(x) = g(f(x)) \in C </tex>.
Проверим, что функция <tex>h(x)</tex> вычислима за полиномиальное время от длины входа. Для вычисления значения функции <tex>h(x)</tex> сначала нужно вычислить <tex>f(x)</tex>. Время вычисления <tex>f(x)</tex> ограничено сверху некоторым полиномом <tex>p_1(|x|)</tex>, т.к. эта функция применяется в сведении по Карпу. Затем нужно вычислить <tex>g(f(x))</tex>. Пусть <tex>t = f(x)</tex>. Т.к. за единицу времени может быть написан лишь один символ, то <tex>|t| < p_1(|x|)</tex>. Время вычисления <tex>g(t)</tex> ограничено сверху некоторым полиномом <tex>p_2(|t|)</tex>. Т.о. время вычисления <tex>h(x)</tex> не больше <tex>p_2(p_1(|x|)) + p_1(|x|)</tex>.
