Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи — различия между версиями
Leugenea (обсуждение | вклад) (Добавил определение сложного языка) |
|||
(не показано 28 промежуточных версий 5 участников) | |||
Строка 1: | Строка 1: | ||
− | + | == Определения == | |
− | |||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | '''Язык <tex>L_1</tex> сводится по Карпу к языку <tex>L_2</tex> (<tex>L_1 \leq L_2</tex>)''', если существует такая функция <tex>f | + | '''Язык <tex>L_1</tex> сводится по Карпу к языку <tex>L_2</tex> (<tex>L_1 \leq L_2</tex>)''', если существует такая функция <tex>f</tex>, работающая за полином, что <tex>x</tex> принадлежит <tex>L_1</tex> тогда и только тогда, когда <tex>f(x)</tex> принадлежит <tex>L_2</tex>. |
− | |||
}} | }} | ||
− | == | + | == Простой пример сведения по Карпу == |
Зададим следующие языки: | Зададим следующие языки: | ||
− | * <tex>IND</tex> — множество пар вида <tex> \langle G, k \rangle </tex>, где <tex>G</tex> — граф, а <tex>k</tex> — число, | + | * <tex>IND</tex> — множество пар вида <tex> \langle G, k \rangle </tex>, где <tex>G</tex> — граф, а <tex>k</tex> — число, такое, что в <tex>G</tex> есть [http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B5%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D0%BE%D0%BC_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B5#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F независимое множество] размера <tex>k</tex>. |
− | * <tex>CLIQUE</tex> — множество пар вида <tex> \langle G, k \rangle </tex>, где <tex>G</tex> — граф, а <tex>k</tex> — | + | * <tex>CLIQUE</tex> — множество пар вида <tex> \langle G, k \rangle </tex>, где <tex>G</tex> — граф, а <tex>k</tex> — число, такое, что в <tex>G</tex> есть [http://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B8%D0%BA%D0%B0_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2) клика] размера <tex>k</tex>. |
− | + | {{Теорема | |
− | Рассмотрим функцию <tex>f( \langle G, k \rangle ) = \langle \overline{G}, k \rangle</tex>, где <tex>\overline{G}</tex> — [http://ru.wikipedia.org/wiki/%D0%94%D0%BE%D0%BF%D0%BE%D0%BB%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B3%D1%80%D0%B0%D1%84%D0%B0 дополнение графа] <tex>G</tex>. <tex>f</tex> вычислима за линейное время от длины входа, если граф | + | |statement= <tex>IND \leq CLIQUE</tex> |
− | * (<tex>x \in L_1 \Rightarrow f(x) \in L_2</tex>) Заметим, что если в <tex>G</tex> было независимое множество размера <tex>k</tex>, то в <tex>\overline{G}</tex> будет клика такого же размера (вершины, которые были в независимом множестве, в <tex>\overline{G}</tex> попарно соединены рёбрами и образуют клику). | + | |proof= |
− | * (<tex>x \in L_1 \Leftarrow f(x) \in L_2</tex>) Обратно, если в <tex>\overline{G}</tex> есть клика размера <tex>k</tex>, то в исходном графе было независимое множество размера <tex>k</tex>. | + | Рассмотрим функцию <tex>f( \langle G, k \rangle ) = \langle \overline{G}, k \rangle</tex>, где <tex>\overline{G}</tex> — [http://ru.wikipedia.org/wiki/%D0%94%D0%BE%D0%BF%D0%BE%D0%BB%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B3%D1%80%D0%B0%D1%84%D0%B0 дополнение графа] <tex>G</tex>. <tex>f</tex> вычислима за линейное время от длины входа, если граф задан в виде матрицы смежности.<br> |
+ | * (<tex>x \in L_1 \Rightarrow f(x) \in L_2</tex>). Заметим, что, если в <tex>G</tex> было независимое множество размера <tex>k</tex>, то в <tex>\overline{G}</tex> будет клика такого же размера (вершины, которые были в независимом множестве, в <tex>\overline{G}</tex> попарно соединены рёбрами и образуют клику). | ||
+ | * (<tex>x \in L_1 \Leftarrow f(x) \in L_2</tex>). Обратно, если в <tex>\overline{G}</tex> есть клика размера <tex>k</tex>, то в исходном графе было независимое множество размера <tex>k</tex>. | ||
Таким образом, <tex>IND \leq CLIQUE</tex> по определению. | Таким образом, <tex>IND \leq CLIQUE</tex> по определению. | ||
+ | }} | ||
+ | '''Замечание.''' Другие примеры сведения по Карпу приведены в статье, содержащей [[Примеры NP-полных языков. Теорема Кука | примеры NP-полных языков]]. | ||
− | + | == Свойства сведения == | |
{{Теорема | {{Теорема | ||
Строка 23: | Строка 25: | ||
|statement=Сведение по Карпу транзитивно, то есть: <tex> ( L_1 \leq L_2, L_2 \leq L_3 ) \Rightarrow L_1 \leq L_3 </tex>. | |statement=Сведение по Карпу транзитивно, то есть: <tex> ( L_1 \leq L_2, L_2 \leq L_3 ) \Rightarrow L_1 \leq L_3 </tex>. | ||
|proof= | |proof= | ||
− | Пусть <tex>f</tex> и <tex>g</tex> — функции из определения сведения для <tex> L_1 \leq L_2 </tex> и <tex> L_2 \leq L_3 </tex> соответственно. Из определения следует: <tex>x \in L_1 \Leftrightarrow f(x) \in L_2 \Leftrightarrow g(f(x)) \in L_3</tex>. | + | Пусть <tex>f</tex> и <tex>g</tex> — функции из определения сведения для <tex> L_1 \leq L_2 </tex> и <tex> L_2 \leq L_3 </tex> соответственно. Из определения следует: <tex>x \in L_1 \Leftrightarrow f(x) \in L_2 \Leftrightarrow g(f(x)) \in L_3</tex>. |
− | Проверим, что <tex>g(f(x))</tex> вычислима за полиномиальное | + | |
− | + | Проверим, что <tex>g(f(x))</tex> вычислима за полиномиальное от <tex>|x|</tex> время.<br/> | |
+ | Действительно, первым делом необходимо вычислить <tex>f(x)</tex>, на это уйдет полином от <tex>|x|</tex> времени.<br/> | ||
+ | Кроме того, длина входа <tex>g</tex>, являющегося выводом <tex>f(x)</tex>, тоже полиномиальна, так как за единицу времени может быть выведено не более, чем константное число символов. Значит, вычисление <tex>g(f(x))</tex> также займет времени не более, чем полином от <tex>|x|</tex>. | ||
+ | |||
+ | Таким образом, полное время работы программы есть сумма полиномов от <tex>|x|</tex> и потому тоже является полиномом от <tex>|x|</tex>. | ||
+ | }} | ||
+ | |||
+ | == Определения трудных и полных задач == | ||
+ | |||
+ | {{Определение | ||
+ | |definition = | ||
+ | <tex>C</tex> — сложностный класс. Язык <tex>L</tex> называется '''<tex>C</tex>-трудным (относительно полиномиального сведения) (<tex>C</tex>-hard)''', если любой язык <tex>M</tex> из <tex>C</tex> сводится по Карпу к <tex>L</tex>:<br> | ||
+ | <tex> (L </tex> — <tex>C</tex>-hard <tex>) \overset{\underset{\mathrm{def}}{}}{\Leftrightarrow} ( \forall M \in C \Rightarrow M \leq L) </tex>. | ||
+ | }} | ||
+ | |||
+ | {{Определение | ||
+ | |definition = | ||
+ | <tex>C</tex> — сложностный класс. Язык <tex>L</tex> называется '''<tex>C</tex>-полным (относительно полиномиального сведения) (<tex>C</tex>-complete)''', если <tex>L</tex> является <tex>C</tex>-трудным и сам лежит в <tex>C</tex>. | ||
+ | }} | ||
+ | |||
+ | == Обобщение на другие ограничения на сведения == | ||
+ | {{Определение | ||
+ | |definition = | ||
+ | <tex>D</tex> — класс языков, распознаваемых программами с некоторыми ограничениями. Тогда обозначим <tex>\widetilde{D}</tex> класс вычислимых функций, вычисляемых программами с теми же ограничениями. | ||
+ | }} | ||
+ | {{Определение | ||
+ | |definition = | ||
+ | '''Язык <tex>L_1</tex> <tex>\widetilde{D}</tex>-сводится по Карпу к языку <tex>L_2</tex> (<tex>L_1 \leq_{\widetilde{D}} L_2</tex>)''', если существует такая функция <tex>f</tex> из <tex>\widetilde{D}</tex>, что <tex>x</tex> принадлежит <tex>L_1</tex> тогда и только тогда, когда <tex>f(x)</tex> принадлежит <tex>L_2</tex>:<br> | ||
+ | <tex> (L_1 \leq_{\widetilde{D}} L_2) \overset{\underset{\mathrm{def}}{}}{\iff} ( \exists f \in \widetilde{D} : x \in L_1 \Leftrightarrow f(x) \in L_2 ) </tex>. | ||
+ | }} | ||
+ | '''Замечание.''' Часто используется сведение из <tex>\widetilde{P}</tex>, поэтому вместо «<tex>\widetilde{P}</tex>-сводится по Карпу» говорят просто «сводится». Также индекс у символа сведения обычно опускают. | ||
+ | |||
+ | {{Лемма | ||
+ | |statement=<tex>(L_1 \leq_{\widetilde{D}} L_2) \Leftrightarrow (\overline {L_1} \leq_{\widetilde{D}} \overline {L_2})</tex> | ||
+ | |id=lemma | ||
+ | |proof= | ||
+ | По определению сведения существует такая функция <tex>f</tex> из класса <tex>\widetilde{D}</tex>, что <tex>x \in L_1 \Leftrightarrow f(x) \in L_2</tex>. Для того, чтобы свести <tex>\overline{L_1}</tex> к <tex>\overline{L_2}</tex> будем использовать ту же функцию <tex>f</tex>.<br> | ||
+ | В самом деле: <tex>( x \in L_1 \Leftrightarrow f(x) \in L_2 ) \iff ( \overline{x \in L_1} \Leftrightarrow \overline{f(x) \in L_2} ) </tex> <tex>\iff ( x \in \overline{L_1} \Leftrightarrow f(x) \in \overline{L_2} ) \iff (\overline {L_1} \leq_{\widetilde{D}} \overline {L_2})</tex>. | ||
}} | }} | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | <tex>C</tex> — сложностный класс, <tex>\widetilde{D}</tex> — | + | <tex>C</tex> — сложностный класс, <tex>\widetilde{D}</tex> — класс вычислимых функций. Язык <tex>L</tex> называется '''<tex>C</tex>-трудным относительно <tex>\widetilde{D}</tex>-сведения (<tex>C</tex>-hard)''', если любой язык <tex>M</tex> из <tex>C</tex> <tex>\widetilde{D}</tex>-сводится к <tex>L</tex>:<br> |
− | <tex> (L </tex> — <tex>C</tex>-hard <tex>) \Leftrightarrow ( \forall M \in C \Rightarrow M \leq_{f} L, f \in \widetilde{D} ) </tex>. | + | <tex> (L </tex> — <tex>C</tex>-hard <tex>) \overset{\underset{\mathrm{def}}{}}{\Leftrightarrow} ( \forall M \in C \Rightarrow M \leq_{f} L, f \in \widetilde{D} ) </tex>. |
}} | }} | ||
+ | |||
+ | {{Определение | ||
+ | |definition = | ||
+ | <tex>C</tex> — сложностный класс, <tex>\widetilde{D}</tex> — класс вычислимых функций. Язык <tex>L</tex> называется '''<tex>C</tex>-полным относительно <tex>\widetilde{D}</tex>-сведения (<tex>C</tex>-complete)''', если <tex>L</tex> является <tex>C</tex>-трудным относительно <tex>\widetilde{D}</tex>-сведения и сам лежит в <tex>C</tex>. | ||
+ | }} | ||
+ | |||
+ | [[Категория: Теория сложности]] |
Версия 17:54, 1 июня 2018
Содержание
Определения
Определение: |
Язык | сводится по Карпу к языку ( ), если существует такая функция , работающая за полином, что принадлежит тогда и только тогда, когда принадлежит .
Простой пример сведения по Карпу
Зададим следующие языки:
- независимое множество размера . — множество пар вида , где — граф, а — число, такое, что в есть
- клика размера . — множество пар вида , где — граф, а — число, такое, что в есть
Теорема: |
Доказательство: |
Рассмотрим функцию дополнение графа . вычислима за линейное время от длины входа, если граф задан в виде матрицы смежности.
|
Замечание. Другие примеры сведения по Карпу приведены в статье, содержащей примеры NP-полных языков.
Свойства сведения
Теорема (о транзитивности): |
Сведение по Карпу транзитивно, то есть: . |
Доказательство: |
Пусть и — функции из определения сведения для и соответственно. Из определения следует: .Проверим, что |
Определения трудных и полных задач
Определение: |
— -hard . | — сложностный класс. Язык называется -трудным (относительно полиномиального сведения) ( -hard), если любой язык из сводится по Карпу к :
Определение: |
— сложностный класс. Язык называется -полным (относительно полиномиального сведения) ( -complete), если является -трудным и сам лежит в . |
Обобщение на другие ограничения на сведения
Определение: |
— класс языков, распознаваемых программами с некоторыми ограничениями. Тогда обозначим класс вычислимых функций, вычисляемых программами с теми же ограничениями. |
Определение: |
Язык . | -сводится по Карпу к языку ( ), если существует такая функция из , что принадлежит тогда и только тогда, когда принадлежит :
Замечание. Часто используется сведение из
, поэтому вместо « -сводится по Карпу» говорят просто «сводится». Также индекс у символа сведения обычно опускают.Лемма: |
Доказательство: |
По определению сведения существует такая функция |
Определение: |
— -hard . | — сложностный класс, — класс вычислимых функций. Язык называется -трудным относительно -сведения ( -hard), если любой язык из -сводится к :
Определение: |
— сложностный класс, — класс вычислимых функций. Язык называется -полным относительно -сведения ( -complete), если является -трудным относительно -сведения и сам лежит в . |