Изменения

Язык <mathtex>A\,\!</mathtex> сводится по Карпу к языку <mathtex>B\,\!</mathtex>, если существует функция <mathtex>f(x)\,\!</mathtex> такая, что <mathtex>x \in A</mathtex> тогда и только тогда, когда <mathtex>f(x) \in bB</mathtex>.

<mathtex>IND\,\!</mathtex> и <mathtex>CLIQUE\,\!</mathtex> <math>–\,\!</math> множество — множества пар <mathtex>\langle G, k \rangle \,\!</mathtex>, где <mathtex>G\,\!</mathtex> – — граф, <mathtex>k\,\!</mathtex> – — натуральное число. Пара <mathtex>\langle G, k \rangle \,\!</mathtex> принадлежит <mathtex>IND\,\!</mathtex>, если в графе <mathtex>G\,\!</mathtex> есть подграф с <mathtex>k\,\!</mathtex> вершинами, в котором все эти вершины не связаны ребрами. Пара <mathtex>\langle G, k \rangle \,\!</mathtex> принадлежит <mathtex>CLIQUE\,\!</mathtex>, если в графе <mathtex>G\,\!</mathtex> есть подграф с <mathtex>k\,\!</mathtex> вершинами, в котором между каждой парой вершин проходит ребро. Существует функция <tex>f</tex> такая, что <tex>f(\langle G, k \rangle ) = \langle H, k \rangle </tex>, где <tex>H</tex> — граф, в котором столько же вершин, сколько и в <tex>G</tex>, а ребра расставлены следующим образом: если в графе <tex>G</tex> между вершинами <tex>u</tex> и <tex>v</tex> есть ребро, то в графе <tex>H</tex> это ребро не проводится, если же в графе <tex>G</tex> между этими вершинами его не было, то в <tex>H</tex> оно есть между соответствующими вершинами. Эта функция вычисляется за линейное время от длины входа, если представлять граф в виде матрицы смежности. Заметим, что если в графе <tex>G</tex> был независимый подграф с <tex>k</tex> вершинами, то в <tex>H</tex> между всеми вершинами подграфа будут ребра, следовательно, в графе <tex>H</tex> будет клика с <tex>k</tex> вершинами.  С другой стороны, если в <tex>H</tex> есть клика с <tex>k</tex> вершинами, значит между всеми вершинами клики проведены ребра, а значит их не было в графе <tex>G</tex>. Таким образом, в графе <tex>G</tex> был независимый подграф с <tex>k</tex> вершинами. Из всего сказанного следует, что <tex>IND \le CLIQUE</tex>. ==Теорема о транзитивности==Операция сведения по Карпу транзитивна. То есть, если <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 \Leftrightarrow f(x) \in B</tex>. Пусть в свою очередь <tex>B \le C</tex> и есть функция <tex>g</tex>: <tex>y \in B \Leftrightarrow g(y) \in C</tex>.

Существует Рассмотрим функция <math>f\,\!</math> такая, что <mathtex>h(x) = g(f(\langle G, k \rangle x)) = \langle H, k \rangle \,\!</mathtex>, где . <mathtex>Hx \,in A \!</math> – граф, в котором столько же вершин, сколько и в <math>GLeftrightarrow f(x) \,\!in B</mathtex>, а ребра расставлены следующим образом: если в графе . Также <mathtex>Gf(x) \,in B \!</math> между вершинами <math>u\,Leftrightarrow g(f(x)) \!in C</math> и <math>v\,\!</mathtex> . То есть ребро, то в графе <mathtex>Hx \,in A \!</math> это ребро не проводится, если же в графе <math>GLeftrightarrow h(x) = g(f(x)) \,\!in C </mathtex> между этими вершинами его не было, то в <math>H\,\!</math> оно есть между соответствующими вершинами. Эта функция вычисляется за линейное время от длины входа, если представлять граф в виде матрицы смежности.

ЗаметимПроверим, что если функция <tex>h(x)</tex> вычислима за полиномиальное время от длины входа. Для вычисления значения функции <tex>h(x)</tex> сначала нужно вычислить <tex>f(x)</tex>. Время вычисления <tex>f(x)</tex> ограничено сверху некоторым полиномом <tex>p_1(|x|)</tex>, так как эта функция применяется в графе сведении по Карпу. Затем нужно вычислить <mathtex>G\,\!g(f(x))</mathtex> был независимый подграф с . Пусть <mathtex>k\,\!t = f(x)</mathtex> вершинами. Так как за единицу времени может быть написан лишь один символ, то в <mathtex>|t| < p_1(|x|)</tex>. Время вычисления <tex>g(t)</tex> ограничено сверху некоторым полиномом <tex>H\,\!p_2(|t|)</mathtex> между всеми вершинами подграфа будут ребра. Таким образом, следовательно, в графе время вычисления <mathtex>H\,\!h(x)</mathtex> будет клика с не больше <mathtex>k\,\!p_2(p_1(|x|)) + p_1(|x|)</mathtex> вершинами.

Из всего сказанного следует, что <math>IND \le CLIQUE\,\!</math>Смотрите также [[сведение по Куку]].