Сведение по Карпу — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
(Определение)
Строка 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

Определение

Язык [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].