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