editor
177
правок
Изменения
Добавил определение
{{Определение
|definition =
'''Язык <tex>L_1</tex> сводится по Карпу к языку <tex>L_2</tex> (<tex>L_1 \leq L_2</tex>)''', если существует такая функция <tex>f(x)</tex>, вычислимая за полиномиальное от длины входа время, что <tex>x</tex> принадлежит <tex>L_1</tex> тогда и только тогда, когда <tex>f(x)</tex> принадлежит <tex>L_2</tex>:<br>
<tex>(L_1 \leq L_2) \Leftrightarrow ( \exists f \in P : x \in L_1 \Leftrightarrow f(x) \in L_2)</tex>.
}}
|definition =
'''Язык <tex>L_1</tex> сводится по Карпу к языку <tex>L_2</tex> (<tex>L_1 \leq L_2</tex>)''', если существует такая функция <tex>f(x)</tex>, вычислимая за полиномиальное от длины входа время, что <tex>x</tex> принадлежит <tex>L_1</tex> тогда и только тогда, когда <tex>f(x)</tex> принадлежит <tex>L_2</tex>:<br>
<tex>(L_1 \leq L_2) \Leftrightarrow ( \exists f \in P : x \in L_1 \Leftrightarrow f(x) \in L_2)</tex>.
}}
