Редукция (теория рекурсии) - Reduction (recursion theory)

В теории вычислимости изучаются многие отношения сводимости (также называемые редукциями , сводимостью и понятиями сводимости ). Они мотивированы вопросом: можно ли при заданных наборах и натуральных числах эффективно преобразовать метод определения членства в метод определения членства в ? Если ответ на этот вопрос утвердительный, то говорят, что он сводится к . ${\ 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 (п)}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle x}$${\ Displaystyle F (х)}$${\ displaystyle x \ in A}$${\ Displaystyle F (х)}$${\ 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 В ^ {(п)}}$${\ 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 В ^ {(\ альфа)}}$${\ 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