В теории вычислимости и теории сложности вычислений редукция — это алгоритм преобразования одной задачи в другую. Достаточно эффективное сведение одной задачи к другой можно использовать, чтобы показать, что вторая задача по крайней мере так же сложна, как и первая.
Интуитивно, проблема 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 также неразрешим.
