Сокращение «многие к одному»

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

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

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

Определения

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

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

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

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

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

Учитывая два набора $A,B\subseteq \mathbb {N}$ один говорит $A$ сводится много-один к $B$ и пишет

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

если существует полная вычислимая функция $f$ с $x\in A$ если только $f(x)\in B$.

Если сокращение «многие к одному» $f$ инъективен пишут , говорят о редукции «один к одному» и $A\leq _{1}B$.

Если сокращение на единицу $f$ сюръективно говорят , $A$ рекурсивно изоморфен ​ $B$ и пишет ^стр.324

$A\equiv B$

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

Если оба $A\leq _{\mathrm {m} }B$ и $B\leq _{\mathrm {m} }A$, говорит один $A$ много -один эквивалент или m- эквивалентен $B$ и пишет

$A\equiv _{\mathrm {m} }B.$

Многоединичная полнота (m-полнота)

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

Степени

Отношение $\equiv _{m}$ действительно является эквивалентностью , ее классы эквивалентности называются m-степеньями и образуют частично упорядоченное множество ${\mathcal {D}}_{m}$ с порядком, индуцированным $\leq _{m}$. ^стр.257

Некоторые свойства m-степеней, некоторые из которых отличаются от аналогичных свойств степеней Тьюринга : ^{стр.555--581}

• На m-степеньях существует четко определенный оператор перехода.
• Единственная m-степень со скачком 0 _m ′ равна 0 _m .
• Есть m градусов $\mathbf {a} >_{m}{\boldsymbol {0}}_{m}'$ где не существует $\mathbf {b}$ где $\mathbf {b} '=\mathbf {a}$.
• Всякий счетный линейный порядок с наименьшим элементом вкладывается в ${\mathcal {D}}_{m}$.
• Теория первого порядка ${\mathcal {D}}_{m}$ изоморфна теории арифметики второго порядка.

Есть характеристика ${\mathcal {D}}_{m}$ как уникальное ЧУ-множество, удовлетворяющее нескольким явным свойствам своих идеалов , подобная характеристика ускользнула от степеней Тьюринга. ^{стр.574--575}

Теорему Майхилла об изоморфизме можно сформулировать следующим образом: «Для всех множеств $A,B$ натуральных чисел, $A\equiv B\iff A\equiv _{1}B$.» Как следствие, $\equiv$ и $\equiv _{1}$ имеют одинаковые классы эквивалентности. ^стр.325 Классы эквивалентности $\equiv _{1}$ называются 1-градусами .

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

Сокращение «многие единицы» часто подвергается ограничениям на ресурсы, например, функция сокращения вычислима за полиномиальное время, логарифмическое пространство, по формуле $AC_{0}$ или $NC_{0}$ схемы или полилогарифмические проекции, в которых каждое последующее понятие редукции слабее предыдущего; см. в разделе «Полиномиальное сокращение времени» и «Уменьшение пространства журнала» подробности .

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

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

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

многие-один

Можно также задаться вопросом об обобщенных случаях редукции многих к одному. Одним из таких примеров является электронная редукция , где мы рассматриваем $f:A\to B$ которые являются рекурсивно перечислимыми, а не ограничиваются рекурсивными $f$. Полученное соотношение сводимости обозначим $\leq _{e}$, и его частичное упорядоченное множество изучалось аналогично степеням Тьюринга. Например, есть набор для прыжков ${\boldsymbol {0}}_{e}^{'}$ для е -градусов. e -степени действительно допускают некоторые свойства, отличающиеся от свойств частично упорядоченного множества степеней Тьюринга, например, вложение ромбовидного графа в приведенные ниже степени. ${\boldsymbol {'}}_{e}$.

Свойства

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

Карпа

Сведение «много-один» за полиномиальное время от проблемы A к проблеме B (обе из которых обычно должны быть проблемами решения ) — это алгоритм с полиномиальным временем для преобразования входных данных для проблемы A во входные данные для проблемы B , такой, что преобразованный проблема имеет тот же результат, что и исходная проблема. Экземпляр x проблемы A можно решить, применив это преобразование для создания экземпляра y проблемы B , передав y в качестве входных данных для алгоритма задачи B и вернув его результат. Сокращение «многие-один» за полиномиальное время также может быть известно как полиномиальные преобразования или сокращения Карпа , названные в честь Ричарда Карпа . Редукция этого типа обозначается $A\leq _{m}^{P}B$ или $A\leq _{p}B$.