В теории вычислимости и теории сложности вычислений , сокращение является алгоритмом для преобразования одной задачи в другую проблему. Достаточно эффективное сокращение от одной проблемы к другой можно использовать, чтобы показать, что вторая проблема, по крайней мере, так же сложна, как и первая.
Интуитивно проблема 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 трудно аппроксимировать с точностью до множителя α / β.
Примеры [ править ]
- Чтобы показать, что проблема решения 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 .
- Э. Р. Гриффор: Справочник по теории вычислимости, Северная Голландия, 1999, ISBN 978-0-444-89882-1 .
