Снижение много-одного - Many-one reduction

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

Редукции многие-единицы - это частный случай и более сильная форма Редукции Тьюринга. При редукции «много-один» оракул (то есть наше решение для B) может быть вызван только один раз в конце, и ответ не может быть изменен. Это означает, что если мы хотим показать, что проблема A может быть сведена к проблеме B, мы можем использовать наше решение для B только один раз в нашем решении для A, в отличие от редукции по Тьюрингу, где мы можем использовать наше решение для B столько раз, сколько необходимо при решении А.

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

Сокращения типа "много-один" впервые использовали Эмиль Пост в статье, опубликованной в 1944 г.^[1] Потом Норман Шапиро использовал ту же концепцию в 1956 году под названием сильная сводимость.^[2]

Определения

Формальные языки

Предполагать А и B находятся формальные языки над алфавиты Σ и Γ соответственно. А много-одно сокращение из А к B это полная вычислимая функция ж : Σ^* → Γ^* который имеет свойство, что каждое слово ш в А если и только если ж(ш) в B.

Если такая функция ж существует, мы говорим, что А является много-один сводимый или же m-сводимый к B и писать

{ displaystyle A leq _ { mathrm {m}} B.}

Если есть инъективный много-однозначная функция редукции, то мы говорим А является 1-сводимый или же однозначно сводимый к B и писать

{ displaystyle A leq _ {1} B.}

Подмножества натуральных чисел

Учитывая два набора ${ Displaystyle А, В substeq mathbb {N}}$ мы говорим ${ displaystyle A}$ является много-один сводимый к ${ displaystyle B}$ и писать

{ displaystyle A leq _ { mathrm {m}} B}

если существует полная вычислимая функция ${ displaystyle f}$ с ${ displaystyle A = f ^ {- 1} (B).}$ Если дополнительно ${ displaystyle f}$ является инъективный мы говорим ${ displaystyle A}$ является 1-сводимый к ${ displaystyle B}$ и писать

{ displaystyle A leq _ {1} B.}

Эквивалентность многих единиц и 1-эквивалентность

Если ${ displaystyle A leq _ { mathrm {m}} B , mathrm {and} , B leq _ { mathrm {m}} A}$ мы говорим ${ displaystyle A}$ является много-один эквивалент или же м-эквивалент к ${ displaystyle B}$ и писать

{ Displaystyle A Equiv _ { mathrm {m}} B.}

Если ${ Displaystyle A leq _ {1} B , mathrm {и} , B leq _ {1} A}$ мы говорим ${ displaystyle A}$ является 1-эквивалент к ${ displaystyle B}$ и писать

{ Displaystyle A Equiv _ {1} B.}

Многоблочная полнота (м-полнота)

Множество B называется много-один полный, или просто м-полный, если только B рекурсивно перечислим, и каждый рекурсивно перечислимый набор А m-сводится к B.

Сокращение на много-один с ограничениями ресурсов

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

Учитывая решение проблемы А и B и алгоритм N который решает экземпляры B, мы можем использовать сокращение многих единиц из А к B решать случаи А в:

время, необходимое для N плюс время, необходимое для сокращения
максимум места, необходимого для N и пространство, необходимое для сокращения

Мы говорим, что класс C языков (или часть набор мощности натуральных чисел) закрыто при сводимости многих единиц если нет редукции из языка в C на язык за пределами C. Если класс замкнут при сводимости многих единиц, то редукция многих единиц может использоваться, чтобы показать, что проблема заключается в C за счет уменьшения проблемы в C к нему. Редукции многие-единицы ценны, потому что большинство хорошо изученных классов сложности закрыты при некотором типе сводимости много-единицы, в том числе п, НП, L, NL, со-НП, PSPACE, EXP, и много других. Однако эти классы не замкнуты относительно произвольных редукций "много-один".

Характеристики

В связи сводимости многих единиц и сводимости 1 равны переходный и рефлексивный и таким образом вызвать Предварительный заказ на powerset натуральных чисел.
${ displaystyle A leq _ { mathrm {m}} B}$ если и только если ${ displaystyle mathbb {N} setminus A leq _ { mathrm {m}} mathbb {N} setminus B.}$
Множество много-одно сводится к проблема остановки если и только если это рекурсивно перечислимый. Это говорит о том, что в отношении сводимости многих единиц проблема остановки является наиболее сложной из всех рекурсивно перечислимых проблем. Таким образом, проблема остановки r.e. полный. Обратите внимание, что это не единственное р. Е. полная проблема.
Специализированная проблема остановки для индивидуальный Машина Тьюринга Т (т.е. набор входов, для которых Т в конце концов останавливается) является много-одним полным, если и только если Т это универсальная машина Тьюринга. Эмиль Пост показал, что существуют рекурсивно перечислимые множества, которые ни разрешимый ни m-полные, следовательно, существуют неуниверсальные машины Тьюринга, отдельные проблемы остановки которых, тем не менее, неразрешимы.