editor
177
правок
Изменения
м
→Определения трудных и сложных задач
{{Определение
|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>L\widetilde{D}</tex> относительно -сводится к <tex>\widetilde{D}L</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>.
}}
