В теории вычислимости и теории сложности вычислений редукция — это алгоритм преобразования одной проблемы в другую. Достаточно эффективное сведение одной проблемы к другой может быть использовано для того, чтобы показать, что вторая проблема по крайней мере так же сложна, как и первая.
Интуитивно, проблема A сводится к проблеме B , если алгоритм для эффективного решения проблемы B (если бы он существовал) мог бы также использоваться как подпрограмма для эффективного решения проблемы A. Когда это верно, решение A не может быть сложнее, чем решение B. «Сложнее» означает наличие более высокой оценки требуемых вычислительных ресурсов в данном контексте (например, более высокая временная сложность , большие требования к памяти, дорогостоящая потребность в дополнительных ядрах аппаратного процессора для параллельного решения по сравнению с однопоточным решением и т. д.). Существование сокращения от A до B можно записать в сокращенной записи A ≤ m B , обычно с нижним индексом у ≤ для указания типа используемого сокращения (m : сокращение отображения , p : полиномиальное сокращение ).
Математическая структура, созданная на основе набора задач с помощью редукций определенного типа, обычно образует предпорядок , классы эквивалентности которого могут использоваться для определения степеней неразрешимости и классов сложности .
Существуют две основные ситуации, когда нам необходимо использовать сокращения:
Очень простой пример сокращения — от умножения до возведения в квадрат . Предположим, что все, что мы умеем делать, это складывать, вычитать, возводить в квадрат и делить на два. Мы можем использовать эти знания в сочетании со следующей формулой, чтобы получить произведение любых двух чисел:
У нас также есть сокращение в другом направлении; очевидно, если мы можем умножить два числа, мы можем возвести число в квадрат. Это, кажется, подразумевает, что эти две проблемы одинаково сложны. Этот вид сокращения соответствует сокращению Тьюринга .
Однако сокращение становится намного сложнее, если мы добавляем ограничение, что мы можем использовать функцию возведения в квадрат только один раз и только в конце. В этом случае, даже если нам разрешено использовать все основные арифметические операции, включая умножение, сокращения в общем случае не существует, потому что для того, чтобы получить желаемый результат в виде квадрата, мы должны сначала вычислить его квадратный корень, и этот квадратный корень может быть иррациональным числом , которое не может быть построено с помощью арифметических операций над рациональными числами. Однако, идя в другом направлении, мы, безусловно, можем возвести число в квадрат всего одним умножением, только в конце. Используя эту ограниченную форму сокращения, мы показали неудивительный результат, что умножение в общем случае сложнее, чем возведение в квадрат. Это соответствует сокращению «многие-один» .
Редукция — это предупорядочение , то есть рефлексивное и транзитивное отношение на P ( N )× P ( N ), где P ( N ) — это множество степеней натуральных чисел .
Как описано в примере выше, существует два основных типа редукций, используемых в вычислительной сложности: редукция «многие-один» и редукция Тьюринга . Редукция «многие-один» отображает экземпляры одной проблемы в экземпляры другой; редукция Тьюринга вычисляет решение одной проблемы, предполагая, что другую проблему легко решить. Редукция «многие-один» является более сильным типом редукции Тьюринга и более эффективна при разделении проблем на различные классы сложности. Однако повышенные ограничения на редукции «многие-один» затрудняют их поиск.
Задача является полной для класса сложности, если каждая задача в классе сводится к этой задаче, и она также находится в самом классе. В этом смысле задача представляет класс, поскольку любое ее решение может, в сочетании с сокращениями, использоваться для решения каждой задачи в классе.
Однако, чтобы быть полезными, сокращения должны быть простыми . Например, вполне возможно свести труднорешаемую NP-полную задачу, такую как проблема булевой выполнимости , к тривиальной задаче, например, определить, равно ли число нулю, заставив машину сокращения решать задачу за экспоненциальное время и выводить ноль только в случае наличия решения. Однако это не дает многого, потому что даже если мы можем решить новую задачу, выполнение сокращения так же сложно, как и решение старой задачи. Аналогично, сокращение, вычисляющее невычислимую функцию, может свести неразрешимую задачу к разрешимой. Как указывает Майкл Сипсер в « Введении в теорию вычислений» : «Сокращение должно быть простым относительно сложности типичных задач в классе [...] Если бы само сокращение было сложным для вычисления, простое решение полной задачи не обязательно дало бы простое решение задач, сводящихся к нему».
Таким образом, соответствующее понятие сокращения зависит от изучаемого класса сложности. При изучении класса сложности NP и более сложных классов, таких как полиномиальная иерархия , используются сокращения за полиномиальное время . При изучении классов в пределах P, таких как NC и NL , используются сокращения в логарифмическом пространстве . Сокращения также используются в теории вычислимости , чтобы показать, разрешимы ли проблемы машинами вообще; в этом случае сокращения ограничиваются только вычислимыми функциями .
В случае задач оптимизации (максимизации или минимизации) мы часто думаем в терминах сокращения, сохраняющего приближение . Предположим, у нас есть две задачи оптимизации, такие, что экземпляры одной задачи могут быть отображены на экземпляры другой таким образом, что почти оптимальные решения экземпляров последней задачи могут быть преобразованы обратно, чтобы дать почти оптимальные решения первой. Таким образом, если у нас есть алгоритм оптимизации (или алгоритм аппроксимации ), который находит близкие к оптимальным (или оптимальные) решения для экземпляров задачи B, и эффективное сохраняющее аппроксимацию сведение от задачи A к задаче B, путем композиции мы получаем алгоритм оптимизации, который выдает близкие к оптимальным решения для экземпляров задачи A. Сведения, сохраняющие аппроксимацию, часто используются для доказательства сложности результатов аппроксимации: если некоторую задачу оптимизации A трудно аппроксимировать (при некотором предположении о сложности) с множителем, лучшим, чем α, для некоторого α, и существует сохраняющее β-аппроксимацию сведение от задачи A к задаче B, мы можем заключить, что задачу B трудно аппроксимировать с множителем α/β.
Следующий пример показывает, как использовать редукцию из проблемы остановки для доказательства того, что язык неразрешим. Предположим, что H ( M , w ) — это проблема определения того, останавливается ли данная машина Тьюринга M (принимая или отклоняя) на входной строке w . Известно, что этот язык неразрешим. Предположим, что E ( M ) — это проблема определения того, является ли язык, принимаемый данной машиной Тьюринга M , пустым (другими словами, принимает ли M какие-либо строки вообще). Мы показываем, что E неразрешима редукцией из H .
Чтобы получить противоречие, предположим, что R является решателем для E . Мы используем это для создания решателя S для H (которого, как мы знаем, не существует). Учитывая входные данные M и w (машина Тьюринга и некоторая входная строка), определим S ( M , w ) со следующим поведением: S создает машину Тьюринга N , которая принимает только если входная строка для N равна w , и M останавливается на входе w , и не останавливается в противном случае. Решатель S теперь может оценить R ( N ), чтобы проверить, является ли язык, принимаемый N пустым. Если R принимает N , то язык, принимаемый N , пуст, поэтому, в частности, M не останавливается на входе w , поэтому S может отклонить. Если R отклоняет N , то язык, принимаемый N , непуст, поэтому M останавливается на входе w , поэтому S может принять. Таким образом, если бы у нас был решатель R для E , мы могли бы создать решатель S для проблемы остановки H ( M , w ) для любой машины M и входа w . Поскольку мы знаем, что такого S не может существовать, то отсюда следует, что язык E также неразрешим.
