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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство транзитивности)
м (rollbackEdits.php mass rollback)
 
(не показано 10 промежуточных версий 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>G</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>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>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>.
 
Пусть <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 \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>.
+
Рассмотрим функция <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

Определение

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

Обычно требуют, чтобы сводящая функция была вычислима за полиномиальное время от длины входа.

Заметим, что в таком случае класс языков [math]P[/math] замкнут относительно сведения по Карпу. Если язык [math]L[/math] не равен пустому языку и не равен [math]\Sigma ^*[/math], то существуют слова [math]x_1 \in L[/math] и [math]x_2 \not\in L[/math]. Сводящая функция [math]f(x)[/math] может решить сводимую задачу [math]M[/math] за полиномиальное время от длины входа и выдать [math]x_1[/math], если [math]x \in M[/math], или [math]x_2[/math], если [math]x \not\in M[/math]

Пример

Рассмотрим следующие языки: [math]IND[/math] и [math]CLIQUE[/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].

Теорема о транзитивности

Операция сведения по Карпу транзитивна. То есть, если [math]A \le B[/math], [math]B \le C[/math], то [math]A \le C[/math].

Доказательство транзитивности

Пусть [math]A \le B[/math]. Тогда существует функция [math]f[/math]: [math]x \in A \Leftrightarrow f(x) \in B[/math]. Пусть в свою очередь [math]B \le C[/math] и есть функция [math]g[/math]: [math]y \in B \Leftrightarrow g(y) \in C[/math].

Рассмотрим функция [math]h(x) = g(f(x))[/math]. [math]x \in A \Leftrightarrow f(x) \in B[/math]. Также [math]f(x) \in B \Leftrightarrow g(f(x)) \in C[/math]. То есть [math]x \in A \Leftrightarrow h(x) = g(f(x)) \in C [/math].

Проверим, что функция [math]h(x)[/math] вычислима за полиномиальное время от длины входа. Для вычисления значения функции [math]h(x)[/math] сначала нужно вычислить [math]f(x)[/math]. Время вычисления [math]f(x)[/math] ограничено сверху некоторым полиномом [math]p_1(|x|)[/math], так как эта функция применяется в сведении по Карпу. Затем нужно вычислить [math]g(f(x))[/math]. Пусть [math]t = f(x)[/math]. Так как за единицу времени может быть написан лишь один символ, то [math]|t| \lt p_1(|x|)[/math]. Время вычисления [math]g(t)[/math] ограничено сверху некоторым полиномом [math]p_2(|t|)[/math]. Таким образом, время вычисления [math]h(x)[/math] не больше [math]p_2(p_1(|x|)) + p_1(|x|)[/math].


Смотрите также сведение по Куку.