51
правка
Изменения
→Доказательство
Операция сведения по Карпу транзитивна. Т.е. если <tex>A \le B</tex>, <tex>B \le C</tex>, то <tex>A \le C</tex>.
==Доказательствотранзитивности==
Пусть <tex>A \le B</tex>. Тогда существует функция <tex>f</tex>: <tex>x \in A \LongArrow f(x) \in B</tex>. Пусть в свою очередь <tex>B \le C</tex> и есть функция <tex>g</tex>: <tex>y \in B \LongArrow g(y) \in C</tex>.
Рассмотрим функция <tex>h(x) = g(f(x))</tex>. <tex>x \in A \LongArrow Longarrow f(x) \in B</tex>. Также <tex>f(x) \in B \LongArrow g(f(x)) \in C</tex>. Т.е. <tex>x \in A \LongArrow 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>.
