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

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

Было высказано предположение , что снижение (теория рекурсии) быть объединены в этой статье. ( Обсудить ) Предлагается с апреля 2021 года.

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

Интуитивно, проблема является приводимым к задаче B , если алгоритм для решения задачи B эффективно (если она существует) также может быть использован в качестве подпрограммы для решения задачи A эффективно. Если это верно, то решение A не может быть сложнее , чем решение B . «Сложнее» означает более высокую оценку требуемых вычислительных ресурсов в данном контексте (например, более высокая временная сложность , более высокие требования к памяти, дорогостоящая потребность в дополнительных ядрах аппаратного процессора для параллельного решения по сравнению с однопоточным решением и т. Д.) . Существование редукции от A к B, может быть записано в сокращенной записи A ≤ _m B , обычно с нижним индексом на ≤, чтобы указать тип используемого сокращения (m: сокращение отображения , p: полиномиальное сокращение ).

Математическая структура, созданная для набора задач редукциями определенного типа, обычно образует предварительный порядок , классы эквивалентности которого могут использоваться для определения степеней неразрешимости и классов сложности .

Введение [ править ]

Есть две основные ситуации, когда нам нужно использовать сокращения:

• Во-первых, мы пытаемся решить проблему, похожую на проблему, которую мы уже решили. В этих случаях часто быстрый способ решения новой проблемы состоит в том, чтобы преобразовать каждый экземпляр новой проблемы в экземпляры старой проблемы, решить их, используя существующее решение, а затем использовать их для получения окончательного решения. Это, пожалуй, наиболее очевидное использование сокращений.
• Во-вторых: предположим, что у нас есть проблема, которую, как мы доказали, трудно решить, и у нас есть аналогичная новая проблема. Мы можем подозревать, что это тоже сложно решить. Мы рассуждаем от противного: предположим, новую проблему легко решить. Тогда, если мы сможем показать, что каждый экземпляр старой проблемы можно легко решить, преобразовав его в примеры новой проблемы и решив их, мы получим противоречие. Это означает, что новая проблема также сложна.

Очень простой пример сокращения - от умножения к возведению в квадрат . Предположим, все, что мы умеем делать, - это складывать, вычитать, брать квадраты и делить на два. Мы можем использовать эти знания в сочетании со следующей формулой, чтобы получить произведение любых двух чисел:

${\ displaystyle a \ times b = {\ frac {\ left (\ left (a + b \ right) ^ {2} -a ^ {2} -b ^ {2} \ right)} {2}}}$

У нас также есть снижение в другом направлении; очевидно, что если мы можем умножить два числа, мы можем возвести их в квадрат. Похоже, это означает, что эти две проблемы одинаково сложны. Такая редукция соответствует редукции Тьюринга .

Однако сокращение станет намного сложнее, если мы добавим ограничение, согласно которому мы можем использовать функцию возведения в квадрат только один раз и только в конце. В этом случае, даже если нам разрешено использовать все основные арифметические операции, включая умножение, никакого сокращения в целом не существует, потому что для получения желаемого результата в виде квадрата мы должны сначала вычислить его квадратный корень, а этот квадрат корень может быть иррациональным числом , как это не может быть построена путем арифметических операций над рациональными числами. Однако, если пойти в другом направлении, мы определенно можем возвести число в квадрат всего одним умножением, только в конце. Используя эту ограниченную форму сокращения, мы показали неудивительный результат, что умножение в целом сложнее, чем возведение в квадрат. Это соответствует${\ displaystyle {\ sqrt {2}}}$много-одно сокращение .

Свойства [ править ]

Редукция - это предварительный порядок , то есть рефлексивное и транзитивное отношение на P ( N ) × P ( N ), где P ( N ) - это набор степеней натуральных чисел .

Виды и применения скидок [ править ]

Как описано в приведенном выше примере, существует два основных типа сокращений, используемых в вычислительной сложности: сокращение до многих единиц и сокращение по Тьюрингу . Редукции по принципу «много-один» отображают экземпляры одной проблемы в экземпляры другой; Редукции Тьюринга вычисляют решение одной проблемы, предполагая, что другую проблему легко решить. Редукция «многие единицы» является более сильным типом редукции по Тьюрингу и более эффективна при разделении проблем на отдельные классы сложности. Однако из-за ужесточения ограничений на сокращение «много-один» их труднее найти.

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

Однако, чтобы быть полезным, сокращения должны быть простыми . Например, вполне возможно свести трудную для решения NP-полную проблему, такую ​​как проблема логической выполнимости, к тривиальной задаче, например, определить, равно ли число нулю, если редукционная машина решит задачу за экспоненциальное время и выдаст ноль. только если есть решение. Однако это не дает многого, потому что, хотя мы можем решить новую проблему, выполнение сокращения так же сложно, как и решение старой проблемы. Точно так же сокращение вычисления невычислимой функции может свести неразрешимую проблему к разрешимой. Как указывает Майкл Сипсер во введении в теорию вычислений: "Сокращение должно быть простым по сравнению со сложностью типичных задач в классе [...] Если бы само сокращение было трудно вычислить, простое решение полной проблемы не обязательно привело бы к легкому решению проблем. сводя к этому ".

Следовательно, подходящее понятие редукции зависит от изучаемого класса сложности. При изучении класса сложности NP и более сложных классов, таких как полиномиальная иерархия , используются сокращения за полиномиальное время . При изучении классов внутри P, таких как NC и NL , используются сокращения пространства журнала . Редукции также используются в теории вычислимости, чтобы показать, разрешимы ли проблемы с помощью машин или нет; в этом случае редукции ограничиваются только вычислимыми функциями .

В случае задач оптимизации (максимизации или минимизации) мы часто думаем в терминах редукции, сохраняющей приближение . Предположим, у нас есть две задачи оптимизации, так что экземпляры одной проблемы могут быть отображены на экземпляры другой, таким образом, что почти оптимальные решения экземпляров последней проблемы могут быть преобразованы обратно, чтобы дать почти оптимальные решения для первой. Таким образом, если у нас есть алгоритм оптимизации (или алгоритм приближения), который находит почти оптимальные (или оптимальные) решения экземпляров проблемы B, и эффективное сокращение с сохранением приближения от проблемы A к задаче B, путем композиции мы получаем алгоритм оптимизации, который дает почти оптимальные решения для экземпляров проблемы A. Сокращения, сохраняющие аппроксимацию, часто используются для доказательства точности результатов аппроксимации : если некоторая задача оптимизации A трудно аппроксимировать (при некотором предположении сложности) с коэффициентом лучше, чем α для некоторого α, и существует сокращение, сохраняющее β-аппроксимацию от от задачи A к задаче B, мы можем сделать вывод, что задачу B трудно аппроксимировать с точностью до множителя α / β.

Примеры [ править ]

• Чтобы показать, что проблема решения P неразрешима, мы должны найти редукцию от проблемы решения, которая, как уже известно, неразрешима, до P. Эта функция редукции должна быть вычислимой функцией . В частности, мы часто показываем, что проблема P неразрешима, показывая, что проблема остановки сводится к P.
• Классы сложности P , NP и PSPACE замкнуты относительно (много-единиц, «Карп») редукций за полиномиальное время .
• Классы сложности L , NL , P , NP и PSPACE закрыты относительно сокращения лог-пространства .

Подробный пример [ править ]

В следующем примере показано, как использовать сокращение из проблемы остановки, чтобы доказать неразрешимость языка. Предположим, что 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 , w ) для любой машины M и входа w . Поскольку мы знаем, что такое 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 .