Изменения
Мелкие фиксы
== Определение сведения Определения ==
{{Определение
|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}}{}}{\iff} ( \exists f \in \widetilde{D} : x \in L_1 \Leftrightarrow f(x) \in L_2 ) </tex>.
}}
{{Определение
|definition =
Сведение относительно <tex>\widetilde{P}</tex> называется '''сведением по Карпу'''.
}}
'''Замечание.''' Часто используется именно сведение по Карпу, поэтому слова «относительно сведения по Карпу» и индекс у символа сведения обычно опускаются. Например, [[Примеры NP-полных языков. Теорема Кука | NP-полные языки]].
== Банальный пример сведения по Карпу ==
{{Определение
|definition =
<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}L</tex> к относительно <tex>L\widetilde{D}</tex>:<br>
<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>.
}}
