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

В теории вычислимости и теории сложности вычислений сокращение «многие единицы» (также называемое сокращением отображений) ^[1]) — это сокращение , которое преобразует экземпляры одной проблемы принятия решения (независимо от того, находится ли экземпляр в $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}$ .

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

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

Определения

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

Предполагать $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$ и пишет ^[4]^стр.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}$ . ^[4]^стр.257

Некоторые свойства m-степеней, некоторые из которых отличаются от аналогичных свойств степеней Тьюринга : ^[4]^{стр.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}$ как уникальное ЧУМ, удовлетворяющее нескольким явным свойствам своих идеалов , подобная характеристика ускользнула от степеней Тьюринга. ^[4]^{стр.574--575}

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

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

Отношения транзитивными сводимости ко многим единицам и 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$ . ^[6]^[7]

Ссылки

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

[Abrahamson2016-1] Jump up to: ^а ^б Абрахамсон, Карл Р. (весна 2016 г.). «Картографические сокращения» . CSCI 6420 – Вычислимость и сложность . Университет Восточной Каролины . Проверено 12 ноября 2021 г.

[2] EL Post, « Рекурсивно перечислимые множества положительных целых чисел и проблемы их решения », Бюллетень Американского математического общества 50 (1944) 284–316

[3] Норман Шапиро, « Степени вычислимости », Труды Американского математического общества 82 , (1956) 281–299

[Odifreddi89-4] Jump up to: ^а ^б ^с ^д ^и П. Одифредди , Классическая теория рекурсии: Теория функций и множеств натуральных чисел (стр.320). Исследования по логике и основам математики, том. 125 (1989), Эльзевир 0-444-87295-7.

[5] С. Ахмад, Встраивание алмаза в $\Sigma _{2}$ Степени перечисления (1991). Журнал символической логики , том 56.

[goldreich-6] Гольдрейх, Одед (2008), Вычислительная сложность: концептуальная перспектива , Cambridge University Press, стр. 59–60, ISBN 9781139472746

[kleinberg-tardos-7] Кляйнберг, Джон ; Тардос, Ева (2006). Алгоритм проектирования . Пирсон Образование. стр. 452–453. ISBN 978-0-321-37291-8 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]