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

В теории вычислимости и теории сложности вычислений , сокращение многих один является сокращением , которое преобразует экземпляры одной задачи принятия решения в случаи второй задачи принятия решения , где экземпляр сводится к в языке , если первый экземпляр был на его языке и не на языке, если первоначальный экземпляр не был на его языке . Таким образом, если мы можем решить, есть ли экземпляры на языке , мы можем решить, есть ли экземпляры на его языке, применяя сокращение и решение . Таким образом, сокращения можно использовать для измерения относительной вычислительной сложности двух задач. Говорят, что это сводится к « если», с точки зрения непрофессионала решить сложнее, чем . То есть любой алгоритм, который решает, также может использоваться как часть (в остальном относительно простой) программы, которая решает . ${\ displaystyle L_ {1}}$ ${\ displaystyle L_ {2}}$ ${\ displaystyle L_ {2}}$ ${\ displaystyle L_ {1}}$ ${\ displaystyle L_ {2}}$ ${\ displaystyle L_ {1}}$ ${\ displaystyle L_ {2}}$ ${\ displaystyle L_ {2}}$ ${\ displaystyle L_ {1}}$ ${\ displaystyle L_ {2}}$ ${\ displaystyle L_ {1}}$ ${\ displaystyle L_ {2}}$ ${\ displaystyle L_ {2}}$ ${\ displaystyle L_ {1}}$ ${\ displaystyle L_ {2}}$ ${\ displaystyle L_ {1}}$

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

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

Редукция «многие единицы» была впервые использована Эмилем Постом в статье, опубликованной в 1944 году. Позже Норман Шапиро использовал ту же концепцию в 1956 году под названием сильная сводимость .

Определения

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

Предположим, что и являются формальными языками над алфавитами и соответственно. Сокращение многих один из к является общей вычислимой функцией , которая обладает свойством , что каждое слово находится в том и только в том случае находится в . ${\ displaystyle A}$ ${\ displaystyle B}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle \ Gamma}$ ${\ displaystyle A}$ ${\ displaystyle B}$ ${\ displaystyle f: \ Sigma ^ {*} \ rightarrow \ Gamma ^ {*}}$ ${\ displaystyle w}$ ${\ displaystyle A}$ ${\ displaystyle f (w)}$ ${\ displaystyle B}$

Если такая функция существует, мы говорим, что она сводится или m-сводится к нескольким единицам, и пишем ${\ displaystyle f}$ ${\ displaystyle A}$ ${\ displaystyle B}$

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

Если есть инъективны функция подавления многих один , то мы говорим , является 1-сводимой или один-один сводимы к и записи ${\ displaystyle B}$

{\ displaystyle A \ leq _ {1} B.}

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

Даны два множества мы говорим , есть много-один сводимы к и записи ${\ Displaystyle А, В \ substeq \ mathbb {N}}$ ${\ displaystyle A}$ ${\ displaystyle B}$

{\ Displaystyle A \ leq _ {\ mathrm {m}} B}

если существует общая вычислимая функция с If дополнительно является инъективны мы говорим является 1-сводимой к и записи ${\ displaystyle f}$ ${\ displaystyle A = f ^ {- 1} (B).}$ ${\ displaystyle f}$ ${\ displaystyle A}$ ${\ 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.}

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

{\ Displaystyle A \ Equiv _ {1} B.}

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

Набор называется полным или просто m-полным , если и только если он рекурсивно перечислим и каждый рекурсивно перечислимый набор m-сводится к . ${\ displaystyle B}$ ${\ displaystyle B}$ ${\ displaystyle A}$ ${\ displaystyle B}$

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

Многие сокращение-один часто подвергаются ресурсным ограничениям, например , что функция редукции вычислима за полиномиальное время, логарифмического пространства, с помощью или схем, или полилогарифмов выступов , где каждое последующее понятие сокращения слабее , чем до; см сокращения полиномиальное время и сокращение лог-пространства для деталей. ${\ displaystyle AC_ {0}}$ ${\ displaystyle NC_ {0}}$

Учитывая проблемы , решения и и алгоритм N , который решает примеры , мы можем использовать много-один сокращение от до решать примеры в: ${\ displaystyle A}$ ${\ displaystyle B}$ ${\ displaystyle B}$ ${\ displaystyle A}$ ${\ displaystyle B}$ ${\ displaystyle A}$

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

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

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

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

Languages

In other projects