stringtranslate.com

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

В теории вычислимости и теории вычислительной сложности редукция многих-одного (также называемая редукцией отображения [1] ) — это редукция , которая преобразует экземпляры одной задачи принятия решения (находится ли экземпляр в ) в другую задачу принятия решения (находится ли экземпляр в ) с помощью вычислимой функции . Редуцированный экземпляр находится в языке тогда и только тогда, когда исходный экземпляр находится в его языке . Таким образом, если мы можем решить, находятся ли экземпляры в языке , мы можем решить, находятся ли экземпляры в его языке, применив редукцию и решив для . Таким образом, редукции можно использовать для измерения относительной вычислительной сложности двух задач. Говорят, что сводится к , если, выражаясь простым языком, по крайней мере так же сложно решить, как . Это означает, что любой алгоритм, который решает , также может быть использован как часть (в противном случае относительно простой) программы, которая решает .

Сокращение многих-единиц является особым случаем и более сильной формой сокращений Тьюринга . [1] При сокращении многих-единиц оракул (то есть наше решение для ) может быть вызван только один раз в конце, и ответ не может быть изменен. Это означает, что если мы хотим показать, что проблема может быть сведена к проблеме , мы можем использовать наше решение для только один раз в нашем решении для , в отличие от сокращений Тьюринга, где мы можем использовать наше решение столько раз, сколько необходимо для решения проблемы членства для данного экземпляра .

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

Определения

Официальные языки

Предположим, что и являются формальными языками над алфавитами и , соответственно. Редукция многих единиц от до является полной вычислимой функцией , которая обладает свойством, что каждое слово находится в тогда и только тогда, когда находится в .

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

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

Если даны два множества, то говорят , что множество-одно сводится к и пишут

если существует полная вычислимая функция с тогда и только тогда .

Если редукция многих единиц является инъекционной , то говорят об редукции единиц и пишут .

Если однозначное сведение является сюръективным , то говорят, что оно рекурсивно изоморфно и записывают [4] с.324

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

Если и , то говорят, что это эквивалент многих-одного или эквивалент m и пишут

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

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

Степени

Отношение действительно является эквивалентностью , его классы эквивалентности называются m-степенями и образуют частично упорядоченное множество с порядком, индуцированным . [4] стр.257

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

Существует характеристика как уникального частично упорядоченного множества, удовлетворяющего нескольким явным свойствам его идеалов , подобная характеристика ускользнула от степеней Тьюринга. [4] стр.574--575

Теорему изоморфизма Майхилла можно сформулировать следующим образом: «Для всех множеств натуральных чисел, ». Как следствие, и имеют те же классы эквивалентности. [4] с.325 Классы эквивалентности называются 1-степенями .

Сокращение числа участников с ограничениями ресурсов

Сокращение многих единиц часто подвергается ограничениям по ресурсам, например, функция сокращения вычисляется за полиномиальное время, в логарифмическом пространстве, с помощью схем или полилогарифмических проекций, где каждое последующее понятие сокращения слабее предыдущего; подробности см. в разделе сокращение за полиномиальное время и сокращение в логарифмическом пространстве .

При наличии задач принятия решений и алгоритма N , который решает примеры , мы можем использовать многоединичное сведение от к для решения примеров в:

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

Расширенные сокращения «многие-один»

Можно также спросить об обобщенных случаях редукции многих-одного. Одним из таких примеров является e-редукция , где мы считаем , что являются рекурсивно перечислимыми вместо того, чтобы ограничиваться рекурсивным . Результирующее отношение редукции обозначается , и его частично упорядоченное множество изучалось в том же ключе, что и степеней Тьюринга. Например, существует множество скачков для e -степеней. E -степени допускают некоторые свойства, отличающиеся от свойств частично упорядоченного множества степеней Тьюринга, например, вложение ромбовидного графа в степени ниже . [5]

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

сокращения карпа

Полиномиальное время много-единичного сведения от задачи A к задаче B (обе из которых обычно должны быть задачами принятия решений ) — это полиномиальное время алгоритма для преобразования входных данных для задачи A во входные данные для задачи B , так что преобразованная задача имеет тот же выход, что и исходная задача. Экземпляр x задачи A может быть решен путем применения этого преобразования для создания экземпляра y задачи B , предоставления y в качестве входных данных алгоритму для задачи B и возврата его выходных данных. Полиномиальные много-единичные сведения также могут быть известны как полиномиальные преобразования или сокращения Карпа , названные в честь Ричарда Карпа . Сведение этого типа обозначается или . [6] [7]

Ссылки

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