Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Определение: |
Язык . | сводится по Карпу к языку ( ), если существует такая функция , вычислимая за полиномиальное от длины входа время, что принадлежит тогда и только тогда, когда принадлежит :