Редукция (сложность) - Reduction (complexity)

Пример редукции от задачи логической выполнимости ( AB ) ∧ (¬ A ∨ ¬ B ∨ ¬ C ) ∧ (¬ ABC ) к проблеме вершинного покрытия . Синие вершины образуют минимальное покрытие вершин, а синие вершины в сером овале соответствуют удовлетворительному заданию истинности исходной формулы.

В теории вычислимости и теории сложности вычислений , сокращение является алгоритмом для преобразования одной задачи в другую проблему. Достаточно эффективное сокращение от одной проблемы к другой можно использовать, чтобы показать, что вторая проблема, по крайней мере, так же сложна, как и первая.

Интуитивно, проблема является приводимым к задаче B , если алгоритм для решения задачи B эффективно (если она существует) также может быть использован в качестве подпрограммы для решения задачи A эффективно. Если это верно, то решение A не может быть сложнее , чем решение B . «Сложнее» означает более высокую оценку требуемых вычислительных ресурсов в данном контексте (например, более высокая временная сложность , более высокие требования к памяти, дорогостоящая потребность в дополнительных ядрах аппаратного процессора для параллельного решения по сравнению с однопоточным решением и т. Д.) . Существование сокращения от A до B может быть записано в сокращенной записи Am 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 какие-либо строки вообще). Покажем , что Е неразрешимо сокращением от H .

Чтобы получить противоречие, предположим , что R представляет собой решающий для Е . Мы будем использовать это, чтобы создать решающий элемент 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 может принять. Таким образом, если мы имели Decider R для E , мы смогли бы произвести Decider S для проблемы остановки H ( М , ш ) для любой машины M и вход ш . Поскольку мы знаем, что такого S не может существовать, отсюда следует, что язык E также неразрешим.

Смотрите также

использованная литература

  • Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест и Клиффорд Штайн, Введение в алгоритмы, MIT Press, 2001, ISBN  978-0-262-03293-3
  • Хартли Роджерс младший: Теория рекурсивных функций и эффективной вычислимости, McGraw-Hill, 1967, ISBN  978-0-262-68052-3 .
  • Питер Бюргиссер: Полнота и редукция в теории алгебраической сложности, Springer, 2000, ISBN  978-3-540-66752-0 .
  • ER Griffor: Справочник по теории вычислимости, Северная Голландия, 1999, ISBN  978-0-444-89882-1 .