Сведение по Карпу
Определение
Язык сводится по Карпу к языку , если существует функция такая, что тогда и только тогда, когда .
Обычно требуют, чтобы сводящая функция была вычислима за полиномиальное время от длины входа.
Пример
Рассмотрим следующие языки: и множество пар , где – граф, – натуральное число. Пара принадлежит , если в графе есть подграф с вершинами, в котором все вершины не связаны ребрами. Пара принадлежит , если в графе есть подграф с вершинами, в котором между каждой парой вершин проходит ребро.
Существует функция такая, что , где – граф, в котором столько же вершин, сколько и в , а ребра расставлены следующим образом: если в графе между вершинами и есть ребро, то в графе это ребро не проводится, если же в графе между этими вершинами его не было, то в оно есть между соответствующими вершинами. Эта функция вычисляется за линейное время от длины входа, если представлять граф в виде матрицы смежности.
Заметим, что если в графе был независимый подграф с вершинами, то в между всеми вершинами подграфа будут ребра, следовательно, в графе будет клика с вершинами.
С другой стороны, если в есть клика с вершинами, значит между всеми вершинами клики проведены ребра, а значит их не было в графе . Т.о. в графе был независимый подграф с вершинами.
Из всего сказанного следует, что .
