Сведение по Карпу — различия между версиями
(→Определение) |
(→Определение) |
||
| Строка 1: | Строка 1: | ||
==Определение== | ==Определение== | ||
Язык <math>A\,\!</math> сводится по Карпу к языку <math>B\,\!</math>, если существует функция <math>f(x)\,\!</math> такая, что <math>x \in A</math> тогда и только тогда, когда <math>f(x) \in b</math>. | Язык <math>A\,\!</math> сводится по Карпу к языку <math>B\,\!</math>, если существует функция <math>f(x)\,\!</math> такая, что <math>x \in A</math> тогда и только тогда, когда <math>f(x) \in b</math>. | ||
| + | |||
| + | Обычно требуют, чтобы сводящая функция была вычислима за полиномиальное время от длины входа. | ||
| + | |||
| + | ==Пример== | ||
| + | Рассмотрим следующие языки: | ||
| + | <math>IND\,\!</math> и <math>CLIQUE\,\!</math> <math>–\,\!</math> множество пар <math>\langle G, k \rangle \,\!</math>, где <math>G\,\!</math> – граф, <math>k\,\!</math> – натуральное число. Пара <math>\langle G, k \rangle \,\!</math> принадлежит <math>IND\,\!</math>, если в графе <math>G\,\!</math> есть подграф с <math>k\,\!</math> вершинами, в котором все вершины не связаны ребрами. Пара <math>\langle G, k \rangle \,\!</math> принадлежит <math>CLIQUE\,\!</math>, если в графе <math>G\,\!</math> есть подграф с <math>k\,\!</math> вершинами, в котором между каждой парой вершин проходит ребро. | ||
| + | |||
| + | Существует функция <math>f\,\!</math> такая, что <math>f(\langle G, k \rangle ) = \langle H, k \rangle \,\!</math>, где <math>H\,\!</math> – граф, в котором столько же вершин, сколько и в <math>G\,\!</math>, а ребра расставлены следующим образом: если в графе <math>G\,\!</math> между вершинами <math>u\,\!</math> и <math>v\,\!</math> есть ребро, то в графе <math>H\,\!</math> это ребро не проводится, если же в графе <math>G\,\!</math> между этими вершинами его не было, то в <math>H\,\!</math> оно есть между соответствующими вершинами. Эта функция вычисляется за линейное время от длины входа, если представлять граф в виде матрицы смежности. | ||
| + | |||
| + | Заметим, что если в графе <math>G\,\!</math> был независимый подграф с <math>k\,\!</math> вершинами, то в <math>H\,\!</math> между всеми вершинами подграфа будут ребра, следовательно, в графе <math>H\,\!</math> будет клика с <math>k\,\!</math> вершинами. | ||
| + | |||
| + | С другой стороны, если в <math>H\,\!</math> есть клика с <math>k\,\!</math> вершинами, значит между всеми вершинами клики проведены ребра, а значит их не было в графе <math>G\,\!</math>. Т.о. в графе <math>G\,\!</math> был независимый подграф с <math>k\,\!</math> вершинами. | ||
| + | |||
| + | Из всего сказанного следует, что <math>IND \le CLIQUE\,\!</math>. | ||
Версия 20:23, 14 марта 2010
Определение
Язык сводится по Карпу к языку , если существует функция такая, что тогда и только тогда, когда .
Обычно требуют, чтобы сводящая функция была вычислима за полиномиальное время от длины входа.
Пример
Рассмотрим следующие языки: и множество пар , где – граф, – натуральное число. Пара принадлежит , если в графе есть подграф с вершинами, в котором все вершины не связаны ребрами. Пара принадлежит , если в графе есть подграф с вершинами, в котором между каждой парой вершин проходит ребро.
Существует функция такая, что , где – граф, в котором столько же вершин, сколько и в , а ребра расставлены следующим образом: если в графе между вершинами и есть ребро, то в графе это ребро не проводится, если же в графе между этими вершинами его не было, то в оно есть между соответствующими вершинами. Эта функция вычисляется за линейное время от длины входа, если представлять граф в виде матрицы смежности.
Заметим, что если в графе был независимый подграф с вершинами, то в между всеми вершинами подграфа будут ребра, следовательно, в графе будет клика с вершинами.
С другой стороны, если в есть клика с вершинами, значит между всеми вершинами клики проведены ребра, а значит их не было в графе . Т.о. в графе был независимый подграф с вершинами.
Из всего сказанного следует, что .
