editor
177
правок
Изменения
Определение полного языка
<tex> (L </tex> — <tex>C</tex>-hard <tex>) \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>.
}}
'''Замечание.''' Часто используется сведение по Карпу, поэтому слова «относительно сведения по Карпу» обычно опускаются. Например, [[Примеры NP-полных языков. Теорема Кука | NP-полные языки]].
