Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Эта статья находится в разработке!
Определение: |
Язык . | сводится по Карпу к языку ( ), если существует такая функция , вычислимая за полиномиальное от длины входа время, что принадлежит тогда и только тогда, когда принадлежит :
Банальный пример сведения по Карпу
Зададим следующие языки:
- независимое множество размера . — множество пар вида , где — граф, а — число, таких, что в есть
- клика размера . — множество пар вида , где — граф, а — опять же, число, таких, что в есть
Докажем, что
Рассмотрим функцию , где — дополнение графа . вычислима за линейное время от длины входа, если граф представлен в видел матрицы смежности.
- ( ) Заметим, что если в было независимое множество размера , то в будет клика такого же размера (вершины, которые были в независимом множестве, в попарно соединены рёбрами и образуют клику).
- ( ) Обратно, если в есть клика размера , то в исходном графе было независимое множество размера .
Таким образом,
по определению.Замечание. Многие другие примеры сведения по Карпу могут быть найдены в статье про примеры NP-полных языков.
Теорема (о транзитивности): |
Сведение по Карпу транзитивно, то есть: . |
Доказательство: |
Пусть В итоге получаем, что итоговое время работы и — функции из определения сведения для и соответственно. Из определения следует: . Проверим, что вычислима за полиномиальное время от . В самом деле, сначала нужно вычислить , на это необходимо не более, чем времени ( — полином). Более того, длина входа в не превышает того же , так как за единицу времени может быть выведен максимум один символ. Значит, вычисление на займёт времени не более, чем . не более, чем . |