Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи

Определение:

Язык [math]L_1[/math] сводится по Карпу к языку [math]L_2[/math] ([math]L_1 \leq L_2[/math]), если существует такая функция [math]f(x)[/math], вычислимая за полиномиальное от длины входа время, что [math]x[/math] принадлежит [math]L_1[/math] тогда и только тогда, когда [math]f(x)[/math] принадлежит [math]L_2[/math]: [math](L_1 \leq L_2) \Leftrightarrow ( \exists f \in P : x \in L_1 \Leftrightarrow f(x) \in L_2)[/math].