Редукция (теория рекурсии)

Было предложено объединить эту статью в « Редукция (сложность)» . ( Обсудить ) Предлагается с апреля 2021 года.

В теории вычислимости изучаются многие отношения сводимости (также называемые редукциями , сводимостью и понятиями сводимости ). Они мотивированы вопросом: возможно ли при заданных наборах и натуральных числах эффективно преобразовать метод определения членства в метод определения членства в ? Если ответ на этот вопрос утвердительный, то говорят, что он сводится к . ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle A}$ ${\ displaystyle B}$

Изучение понятий сводимости мотивировано изучением проблем принятия решений . Для многих понятий сводимости, если любое невычислимое множество сводится к набору, то оно также должно быть невычислимым. Это дает мощный метод доказательства невычислимости многих множеств.${\ displaystyle A}$${\ displaystyle A}$

Отношения сводимости [ править ]

Отношение сводимости является бинарным отношением множеств натуральных чисел, является

• Рефлексивный : каждый набор сводится к самому себе.
• Транзитивный : если набор сводится к набору и сводится к набору, то сводится к .${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle C}$${\ displaystyle A}$${\ displaystyle C}$

Эти два свойства подразумевают, что сводимость является предварительным порядком на множестве степеней натуральных чисел. Однако не все предзаказы рассматриваются как понятия сводимости. Понятия, изучаемые в теории вычислимости, обладают неформальным свойством, которое сводится к тому и только тогда, когда любая (возможно, неэффективная) процедура принятия решения для может быть эффективно преобразована в процедуру принятия решения для . Различные отношения сводимости различаются в зависимости от методов, которые они позволяют использовать в таком процессе преобразования. ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle A}$

Степени отношения сводимости [ править ]

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

Степени любого отношения сводимости частично упорядочиваются этим отношением следующим образом. Позвольте быть отношение сводимости и пусть и быть двумя его степенями. Тогда , если и только если существует множество в и набор в таких , что . Это эквивалентно тому свойство , что для каждого набора в и каждом наборе в , , потому что любые два множества в C эквивалентны и любые два множества эквивалентны. Обычно, как показано здесь, для обозначения степеней используются полужирные обозначения.${\ displaystyle \ leq}$${\ displaystyle C}$${\ displaystyle D}$${\ Displaystyle C \ leq D}$${\ displaystyle A}$${\ displaystyle C}$${\ displaystyle B}$${\ displaystyle D}$${\ Displaystyle A \ leq B}$${\ displaystyle A}$${\ displaystyle C}$${\ displaystyle B}$${\ displaystyle D}$${\ Displaystyle A \ leq B}$${\ displaystyle D}$

Сводимость по Тьюрингу [ править ]

Самым фундаментальным понятием сводимости является сводимость по Тьюрингу . Набор натуральных чисел сводится по Тьюрингу к множеству тогда и только тогда, когда существует машина Тьюринга оракула, которая при запуске с ее множеством оракулов будет вычислять индикаторную функцию (характеристическую функцию) . Эквивалентный сводится по Тьюрингу к тогда и только тогда , когда существует алгоритм для вычисления функции индикатора для при условии , что алгоритм снабжен средством , чтобы правильно ответить на вопросы в форме «Есть в ?». ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle n}$${\ displaystyle B}$

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

Редукции сильнее сводимости Тьюринга [ править ]

Сильные сводимости включают

• Однозначная сводимость : однозначно сводится к, если существует вычислимая взаимно однозначная функция с для всех .${\ displaystyle A}$${\ displaystyle B}$ ${\ displaystyle f}$${\ Displaystyle А (х) = В (е (х))}$${\ displaystyle x}$
• Много-один сводимость : есть много-один сводится к , если существует вычислимая функция с для всех .${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle f}$${\ Displaystyle А (х) = В (е (х))}$${\ displaystyle x}$
• Истина-таблица приводимым : истина стол сводится к если Тьюринг сводится к через один (Oracle) Тьюринга машина , которая производит общую функцию по отношению к каждому оракулу.${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$
• Слабая сводимая таблица истинности : сводится ли слабая таблица истинности к, если существует редукция Тьюринга от до и вычислимая функция, которая ограничивает использование . Всякий раз, когда таблица истинности сводится к , также сводится слабая таблица истинности к , поскольку можно построить вычислимую границу использования, учитывая максимальное использование по дереву всех оракулов, которое будет существовать, если сокращение является полным для всех оракулов. .${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle f}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$
• Положительно сводимо: положительно сводится к тому и только тогда, когда таблица истинности сводится к так, чтобы можно было вычислить для каждого формулу, состоящую из атомов такой формы , что эти атомы объединены с помощью и и или, где и из и является 1 , если и и так далее.${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle x}$${\ Displaystyle В (0), В (1), ...}$${\ displaystyle a}$${\displaystyle b}$${\displaystyle a=1}$${\displaystyle b=1}$
• Сводимость перечисления : аналогична положительной сводимости, относящаяся к эффективной процедуре перечисления от до .${\displaystyle A}$${\displaystyle B}$
• Дизъюнктивная сводимая: подобна положительной сводимой с дополнительным ограничением, которое разрешено только или.
• Конъюнктивная сводимость: аналогична положительной сводимости с дополнительным ограничением, которое разрешено только и.
• Линейная сводимость: аналогична положительной сводимости, но с ограничением, что все атомы формы объединяются исключающими или . Другими словами, линейно сводится к тому и только тогда, когда вычислимая функция вычисляет для каждого конечное множество, заданное как явный список чисел, такой, что если и только если содержит нечетное количество элементов .${\displaystyle B(n)}$${\displaystyle A}$${\displaystyle B}$${\displaystyle x}$${\displaystyle F(x)}$${\displaystyle x\in A}$${\displaystyle F(x)}$${\displaystyle B}$

Многие из них были введены Постом (1944). Пост искал невычислимое , вычислимо перечислимое множество, к которому Тьюринг не мог свести проблему остановки . Поскольку в 1944 году он не смог построить такое множество, он вместо этого работал над аналогичными проблемами для различных введенных им сводимостей. С тех пор эти сводимости стали предметом множества исследований, и между ними известно множество взаимосвязей.

Ограниченные сводимости [ править ]

Ограниченная может быть определена форма каждого из указанных выше сильных сводимость. Самые известные из них - это ограниченная редукция таблицы истинности, но есть также ограниченная таблица Тьюринга, ограниченная слабая таблица истинности и другие. Эти первые три являются наиболее распространенными и зависят от количества запросов. Например, набор является ограниченной истиной стол сводится к тогда и только тогда , когда машина Тьюринга вычисления относительно вычисляет список до номеров, запросы по этим номерам , а затем завершается для всех возможных ответов оракула; значение является константой, не зависящей от . Разница между ограниченной слабой таблицей истинности и ограниченной редукцией Тьюринга состоит в том, что в первом случае до${\displaystyle A}$${\displaystyle B}$${\displaystyle M}$${\displaystyle A}$${\displaystyle B}$${\displaystyle n}$${\displaystyle B}$${\displaystyle n}$${\displaystyle x}$${\displaystyle n}$запросы должны выполняться одновременно, в то время как во втором случае запросы могут выполняться один за другим. По этой причине существуют случаи, когда ограниченная таблица истинности сводится к, но не слабая таблица истинности .${\displaystyle A}$${\displaystyle B}$${\displaystyle B}$

Сильное снижение вычислительной сложности [ править ]

Перечисленные выше строгие сокращения ограничивают способ доступа к информации оракула с помощью процедуры принятия решения, но не ограничивают иным образом доступные вычислительные ресурсы. Таким образом , если множество является разрешимым , то сводится к любому набору при любом сильных сводимость , перечисленных выше, даже если не полиномиальное время или экспоненциального время разрешимо. Это приемлемо при изучении теории вычислимости, которая интересуется теоретической вычислимостью, но нецелесообразно для теории вычислительной сложности , изучающей, какие множества могут быть решены при определенных асимптотических ограничениях ресурсов. ${\displaystyle A}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$

Наиболее распространенная сводимость в теории сложности вычислений - сводимость за полиномиальное время ; набор A полиномиально сводится к множеству, если существует функция f за полиномиальное время, такая что для каждого , находится в том и только тогда, когда находится в . Эта сводимость, по сути, является версией сводимости «многие-единицы» с ограниченными ресурсами. Другие ограниченные ресурсами сводимости используются в других контекстах теории вычислительной сложности, где другие ограничения ресурсов представляют интерес.${\displaystyle B}$${\displaystyle n}$${\displaystyle n}$${\displaystyle A}$${\displaystyle f(n)}$${\displaystyle B}$

Редукции слабее сводимости Тьюринга [ править ]

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

• Арифметическая сводимость : множество является арифметическим в наборе, если оно определимо по стандартной модели арифметики Пеано с дополнительным предикатом для . Эквивалентный, согласно теореме Поста , является арифметическим в том и только тогда , когда Тьюринг сводится к , то ю Тьюринга прыжок из , для некоторого натурального числа . Арифметическая иерархия дает более точную классификацию арифметической сводимости.${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B^{(n)}}$${\displaystyle n}$${\displaystyle B}$${\displaystyle n}$
• Гиперарифметическая сводимость : набор является гиперарифметическим в наборе, если он определим (см. Аналитическую иерархию ) по стандартной модели арифметики Пеано с предикатом для . Эквивалентное является гиперарифметической в том и только в том случае Тьюринга сводится к , то й Тьюринг прыжок из , для некоторых - рекурсивный порядковое .${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle \Delta _{1}^{1}}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B^{(\alpha )}}$${\displaystyle a}$${\displaystyle B}$${\displaystyle B}$ ${\displaystyle a}$
• Относительная конструктивность : набор относительно конструируем из набора, если он входит в наименьшую транзитивную модель теории множеств ZFC, содержащую и все ординалы.${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle L(B)}$${\displaystyle B}$

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

• К. Амбос-Спис и П. Фейер, 2006. « Степени неразрешимости ». Неопубликованный препринт.
• П. Одифредди, 1989. Классическая теория рекурсии , Северная Голландия. ISBN  0-444-87295-7
• П. Одифредди, 1999. Классическая теория рекурсии, том II , Elsevier. ISBN 0-444-50205-X 
• Э. Пост, 1944, «Рекурсивно перечислимые множества натуральных чисел и проблемы их решения», Бюллетень Американского математического общества , том 50, страницы 284–316.
• Х. Роджерс мл., 1967. Теория рекурсивных функций и эффективная вычислимость , второе издание 1987 г., MIT Press. ISBN 0-262-68052-1 (мягкая обложка), ISBN 0-07-053522-1  
• Г. Сакс, 1990. Высшая теория рекурсии , Springer-Verlag. ISBN 3-540-19305-7