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

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

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

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

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

Определения [ править ]

Формальные языки [ править ]

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

Если такая функция F существует, то мы говорим , что это много-один приводимая или м-сводим к B и записям

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

Если существует инъективная функция приведения к множеству единиц, то мы говорим, что A является 1-сводимым или однозначно сводимым к 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.}$

Полнота многих единиц (м-полнота) [ править ]

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

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

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

Учитывая проблемы решения A и B и алгоритм N, который решает экземпляры B, мы можем использовать сокращение «многие единицы» от A до B для решения экземпляров 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-полными, и, следовательно, существуют неуниверсальные машины Тьюринга, индивидуальные проблемы остановки которых, тем не менее, неразрешимы .

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