editor
177
правок
Изменения
Добавил определение
{{В разработке}}
== Определения ==
{{Определение
|definition =
<tex>D</tex> — множество языков, <tex>\widetilde{D}</tex> — '''сведение''' — класс функций, соответствующих языкам из <tex>D</tex>.
'''Язык <tex>L_1</tex> сводится к языку <tex>L_2</tex> относительно <tex>\widetilde{D}</tex> (<tex>L_1 \leq_{\widetilde{D}} L_2</tex>)''', если существует такая функция <tex>f(x)</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}}{}}{\Leftrightarrow} ( \exists f \in \widetilde{D} : x \in L_1 \Leftrightarrow f(x) \in L_2 ) </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>.
