Сокращение (сложность)

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

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

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

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

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

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

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

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

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

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

См. также [ править ]

Ссылки [ править ]

Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест и Клиффорд Стейн, Введение в алгоритмы, 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 .