Сведение по Карпу
Определение
Язык сводится по Карпу к языку , если существует функция такая, что тогда и только тогда, когда .
Язык [math]A[/math] сводится по Карпу к языку [math]B[/math], если существует функция [math]f(x)[/math] такая, что [math]x \in A[/math] тогда и только тогда, когда [math]f(x) \in b[/math].
