Сведение по Карпу — различия между версиями
(→Теорема) |
м (rollbackEdits.php mass rollback) |
||
(не показано 12 промежуточных версий 3 участников) | |||
Строка 4: | Строка 4: | ||
Обычно требуют, чтобы сводящая функция была вычислима за полиномиальное время от длины входа. | Обычно требуют, чтобы сводящая функция была вычислима за полиномиальное время от длины входа. | ||
− | Заметим, что в таком случае класс языков <tex>P</tex> замкнут относительно сведения по Карпу, | + | Заметим, что в таком случае класс языков <tex>P</tex> замкнут относительно сведения по Карпу. Если язык <tex>L</tex> не равен пустому языку и не равен <tex>\Sigma ^*</tex>, то существуют слова <tex>x_1 \in L</tex> и <tex>x_2 \not\in L</tex>. Сводящая функция <tex>f(x)</tex> может решить сводимую задачу <tex>M</tex> за полиномиальное время от длины входа и выдать <tex>x_1</tex>, если <tex>x \in M</tex>, или <tex>x_2</tex>, если <tex>x \not\in M</tex> |
==Пример== | ==Пример== | ||
Рассмотрим следующие языки: | Рассмотрим следующие языки: | ||
− | <tex>IND</tex> и <tex>CLIQUE</tex> — множества пар <tex>\langle G, k \rangle </tex>, где <tex>G</tex> — граф, <tex>k</tex> — натуральное число. Пара <tex>\langle G, k \rangle </tex> принадлежит <tex>IND</tex>, если в графе <tex>G</tex> есть подграф с <tex>k</tex> вершинами, в котором все вершины не связаны ребрами. Пара <tex>\langle G, k \rangle </tex> принадлежит <tex>CLIQUE</tex>, если в графе <tex>G</tex> есть подграф с <tex>k</tex> вершинами, в котором между каждой парой вершин проходит ребро. | + | <tex>IND</tex> и <tex>CLIQUE</tex> — множества пар <tex>\langle G, k \rangle </tex>, где <tex>G</tex> — граф, <tex>k</tex> — натуральное число. Пара <tex>\langle G, k \rangle </tex> принадлежит <tex>IND</tex>, если в графе <tex>G</tex> есть подграф с <tex>k</tex> вершинами, в котором все эти вершины не связаны ребрами. Пара <tex>\langle G, k \rangle </tex> принадлежит <tex>CLIQUE</tex>, если в графе <tex>G</tex> есть подграф с <tex>k</tex> вершинами, в котором между каждой парой вершин проходит ребро. |
Существует функция <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>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> оно есть между соответствующими вершинами. Эта функция вычисляется за линейное время от длины входа, если представлять граф в виде матрицы смежности. | ||
Строка 14: | Строка 14: | ||
Заметим, что если в графе <tex>G</tex> был независимый подграф с <tex>k</tex> вершинами, то в <tex>H</tex> между всеми вершинами подграфа будут ребра, следовательно, в графе <tex>H</tex> будет клика с <tex>k</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>H</tex> есть клика с <tex>k</tex> вершинами, значит между всеми вершинами клики проведены ребра, а значит их не было в графе <tex>G</tex>. Таким образом, в графе <tex>G</tex> был независимый подграф с <tex>k</tex> вершинами. |
Из всего сказанного следует, что <tex>IND \le CLIQUE</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 \ | + | Пусть <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>. |
− | Рассмотрим функция <tex>h(x) = g(f(x))</tex>. <tex>x \in A \ | + | Рассмотрим функция <tex>h(x) = g(f(x))</tex>. <tex>x \in A \Leftrightarrow f(x) \in B</tex>. Также <tex>f(x) \in B \Leftrightarrow g(f(x)) \in C</tex>. То есть <tex>x \in A \Leftrightarrow 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>. | ||
+ | |||
+ | ---- | ||
+ | |||
+ | Смотрите также [[сведение по Куку]]. |
Текущая версия на 19:41, 4 сентября 2022
Определение
Язык
сводится по Карпу к языку , если существует функция такая, что тогда и только тогда, когда .Обычно требуют, чтобы сводящая функция была вычислима за полиномиальное время от длины входа.
Заметим, что в таком случае класс языков
замкнут относительно сведения по Карпу. Если язык не равен пустому языку и не равен , то существуют слова и . Сводящая функция может решить сводимую задачу за полиномиальное время от длины входа и выдать , если , или , еслиПример
Рассмотрим следующие языки:
и — множества пар , где — граф, — натуральное число. Пара принадлежит , если в графе есть подграф с вершинами, в котором все эти вершины не связаны ребрами. Пара принадлежит , если в графе есть подграф с вершинами, в котором между каждой парой вершин проходит ребро.Существует функция
такая, что , где — граф, в котором столько же вершин, сколько и в , а ребра расставлены следующим образом: если в графе между вершинами и есть ребро, то в графе это ребро не проводится, если же в графе между этими вершинами его не было, то в оно есть между соответствующими вершинами. Эта функция вычисляется за линейное время от длины входа, если представлять граф в виде матрицы смежности.Заметим, что если в графе
был независимый подграф с вершинами, то в между всеми вершинами подграфа будут ребра, следовательно, в графе будет клика с вершинами.С другой стороны, если в
есть клика с вершинами, значит между всеми вершинами клики проведены ребра, а значит их не было в графе . Таким образом, в графе был независимый подграф с вершинами.Из всего сказанного следует, что
.Теорема о транзитивности
Операция сведения по Карпу транзитивна. То есть, если
, , то .Доказательство транзитивности
Пусть
. Тогда существует функция : . Пусть в свою очередь и есть функция : .Рассмотрим функция
. . Также . То есть .Проверим, что функция
вычислима за полиномиальное время от длины входа. Для вычисления значения функции сначала нужно вычислить . Время вычисления ограничено сверху некоторым полиномом , так как эта функция применяется в сведении по Карпу. Затем нужно вычислить . Пусть . Так как за единицу времени может быть написан лишь один символ, то . Время вычисления ограничено сверху некоторым полиномом . Таким образом, время вычисления не больше .Смотрите также сведение по Куку.