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

Тип сокращения Тьюринга

В теории вычислимости и теории вычислительной сложности редукция « многие к одному» (также называемая редукцией отображения ^[1] ) — это редукция , которая преобразует экземпляры одной проблемы принятия решения (независимо от того, находится ли экземпляр в ) в другую проблему принятия решения (независимо от того, находится ли экземпляр в ). используя эффективную функцию. Сокращенный экземпляр находится на языке тогда и только тогда, когда исходный экземпляр находится на его языке . Таким образом, если мы можем решить, имеются ли экземпляры в языке , мы можем решить, находятся ли экземпляры в его языке, применив сокращение и найдя решение для . Таким образом, сокращения можно использовать для измерения относительной вычислительной сложности двух задач. Говорят, что это сводится к if, с точки зрения непрофессионала, по крайней мере, так же сложно решить, как и . Это означает, что любой решающий алгоритм может также использоваться как часть (в остальном относительно простой) программы, решающей . ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\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}}$

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

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

Определения

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

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

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

Даны два множества, которые можно свести к числу « многие-один», и пишут ${\displaystyle A,B\subseteq \mathbb {N} }$ ${\displaystyle A}$ ${\displaystyle B}$

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

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

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

Если редукция «многие один» сюръективна , говорят , что рекурсивно изоморфна и пишут ^{[4], стр.324.} ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle B}$

${\displaystyle A\equiv B}$

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

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

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

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

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

Степени

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

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

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

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

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

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

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

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

Продлены скидки «много-один»

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

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

• Отношения сводимости ко многим единицам и 1-сводимости являются транзитивными и рефлексивными и, таким образом , вызывают предварительный порядок в множестве степеней натуральных чисел.
• ${\displaystyle A\leq _{\mathrm {m} }B}$ если и только если ${\displaystyle \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 и вернув его выходные данные. Сокращение «многие-единицы» за полиномиальное время также может быть известно как полиномиальные преобразования или сокращения Карпа , названные в честь Ричарда Карпа . Редукция этого типа обозначается или . ^{[6] [7]} ${\displaystyle A\leq _{m}^{P}B}$ ${\displaystyle A\leq _{p}B}$

Рекомендации

1. Абрахамсон, Карл Р. (весна 2016 г.). «Картографические сокращения». CSCI 6420 – Вычислимость и сложность . Университет Восточной Каролины . Проверено 12 ноября 2021 г.
2. EL Post, «Рекурсивно перечислимые множества положительных целых чисел и проблемы их решения», Бюллетень Американского математического общества 50 (1944) 284–316
3. Норман Шапиро, «Степени вычислимости», Труды Американского математического общества 82 , (1956) 281–299
4. П. Одифредди, Классическая теория рекурсии: Теория функций и множеств натуральных чисел (стр.320). Исследования по логике и основам математики, том. 125 (1989), Эльзевир 0-444-87295-7.
5. С. Ахмад, Вложение ромба в степени перечисления (1991). Журнал символической логики, том 56.
6. Гольдрейх, Одед (2008), Вычислительная сложность: концептуальная перспектива , Cambridge University Press, стр. 59–60, ISBN 9781139472746
7. Кляйнберг, Джон ; Тардос, Ева (2006). Алгоритм проектирования . Пирсон Образование. стр. 452–453. ISBN 978-0-321-37291-8.