Язык \(L\) полиномиально сводится к языку \(K\), если существует вычислимая за полиномиальное время функция \(f\), для которой \(w\in L\iff f(w)\in K\). В обозначениях пособия это записывается
Сводимость показывает, что задача \(L\) не сложнее \(K\) с точностью до полиномиальных затрат на преобразование входа. Поэтому если \(L\prec K\) и \(K\in P\), то \(L\in P\). Сводимость
Что важно запомнить
- Сведение — полиномиально вычислимое преобразование экземпляров одной задачи в экземпляры другой.
- Условие корректности: \(w\in L\iff f(w)\in K\).
- Направление \(L\prec K\) означает: имея эффективный алгоритм для \(K\), можно эффективно решить \(L\).
- Если \(L\prec K\) и \(K\prec H\), то
- Если \(K\in P\) и \(L\prec K\), то \(L\in P\).
Определение
Пусть \(L\) и \(K\) — языки, кодирующие две задачи распознавания. Полиномиальная сводимость \(L\prec K\) означает существование функции \(f\), вычисляемой детерминированной МТ за полиномиальное время, такой что
\(w\in L\iff f(w)\in K.\)
Функция \(f\) должна преобразовывать и положительные, и отрицательные экземпляры корректно. Она не обязана решать \(K\), а только строит новый вход.
Это many-one, или карповская, сводимость: каждому исходному входу соответствует один преобразованный вход \(f(w)\). Она не использует многократные запросы к решателю задачи \(K\), поэтому её не следует смешивать с более общими оракульными (Turing) reductions.
Почему направление важно
Чтобы использовать алгоритм задачи \(K\) для решения \(L\), сначала вычисляют \(f(w)\), затем запускают алгоритм для \(K\). Поэтому именно \(L\prec K\) позволяет переносить верхнюю оценку сложности от \(K\) к \(L\). Если \(K\in P\), композиция двух полиномиальных алгоритмов остаётся полиномиальной, значит
Транзитивность
Если \(L\prec K\) через \(f\), а \(K\prec H\) через \(g\), то композиция \(g(f(w))\) также вычисляется за полиномиальное время и сохраняет ответ да/нет. Следовательно,
Именно транзитивность позволяет строить цепочки доказательств NP-полноты: после появления одной исходной NP-полной задачи новые задачи удобно сравнивать с ней через последовательность редукций.
Пример простыми словами
Если мы умеем за полиномиальное время преобразовать любую КНФ \(K\) в 3-КНФ \(K'\), причём \(K\) выполнима тогда и только тогда, когда \(K'\) выполнима, то получено сведение SAT к 3-SAT. Алгоритм решения 3-SAT после такого преобразования автоматически дал бы алгоритм решения SAT.
Частые ошибки
- Переворачивать направление редукции. Для доказательства трудности \(K\) к ней сводят уже известную трудную задачу \(L\), а не наоборот.
- Требовать, чтобы \(f(w)\) была решением исходной задачи. Это только новый экземпляр задачи \(K\).
- Использовать преобразование, которое не сохраняет ответы да/нет или само требует сверхполиномиального времени.
- Смешивать many-one сведение курса с оракульной сводимостью, где алгоритм может многократно обращаться к решателю другой задачи.
