Снижение много-одного

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

• 1 Определения
  • 1.1 Формальные языки
  • 1.2 Подмножества натуральных чисел
  • 1.3 Эквивалентность многих единиц и 1-эквивалентность
  • 1.4 Полнота по множеству единиц (m-полнота)
• 2 Сокращение по принципу "много-один" с ограничениями ресурсов
• 3 свойства
• 4 ссылки

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

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