Войти
Пример редукции из задачи логической выполнимости (A B) ∧ (¬A ∨ ¬B ∨ ¬C) ∧ (¬A ∨ B ∨ C) к задаче о вершинном покрытии. Синие вершины образуют минимальное покрытие вершин, а синие вершины в сером овале соответствуют удовлетворяющему назначению истинности для исходной формулы. В теории вычислимости и теория вычислительной сложности, сокращение - это алгоритм для преобразования одной задачи в другую проблему. Достаточно эффективное сокращение от одной проблемы к другой можно использовать, чтобы показать, что вторая проблема, по крайней мере, так же сложна, как и первая.
Интуитивно проблема A сводится к проблеме B, если алгоритм для эффективного решения проблемы B (если он существует) может также использоваться в качестве подпрограммы для эффективного решения проблемы A. Когда это так, решение A не может быть сложнее, чем решение B. «Сложнее» означает более высокую оценку требуемых вычислительных ресурсов в данном контексте (например, более высокая временная сложность, более высокие требования к памяти, дорогостоящие потребности для дополнительных ядер процессора для параллельного решения по сравнению с однопоточным решением и т. д.). Существование сокращения от A до B может быть записано в сокращенной записи A ≤ m B, обычно с нижним индексом на ≤, чтобы указать тип используемого сокращения (m: сокращение отображения, p: полиномиальная редукция ).
Математическая структура, созданная для набора задач редукциями определенного типа, обычно образует предварительный заказ, классы эквивалентности которого могут использоваться для определения степени неразрешимости и классы сложности.
Есть две основные ситуации, когда нам нужно использовать сокращения:
Очень простой пример сокращения - от умножения к возведению в квадрат. Предположим, все, что мы умеем делать, это складывать, вычитать, брать квадраты и делить на два. Мы можем использовать это знание в сочетании со следующей формулой, чтобы получить произведение любых двух чисел:
У нас также есть редукция в другом направлении; очевидно, если мы можем умножить два числа, мы можем возвести их в квадрат. Похоже, это означает, что эти две проблемы одинаково сложны. Такое сокращение соответствует редукции по Тьюрингу.
. Однако сокращение станет намного сложнее, если мы добавим ограничение, согласно которому мы можем использовать функцию возведения в квадрат только один раз и только в конце. В этом случае, даже если нам разрешено использовать все основные арифметические операции, включая умножение, никакого сокращения в целом не существует, потому что для получения желаемого результата в виде квадрата мы должны сначала вычислить его квадратный корень, а этот квадрат root может быть иррациональным числом, например 
Редукция - это предварительный заказ, то есть рефлексивное и транзитивное отношение на 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 также неразрешим.
