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

В теория вычислимости, много отношения сводимости (также называемый сокращение, сводимости, и понятия сводимости) изучаются. Их мотивирует вопрос: данные наборы А и B натуральных чисел, можно ли эффективно преобразовать метод определения принадлежности к B в метод определения членства в А? Если ответ на этот вопрос утвердительный, то А как говорят сводится к B.

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

Отношения сводимости

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

Рефлексивный: Каждый набор сводится к самому себе.
Переходный: Если набор А сводится к множеству B и B сводится к множеству C тогда А сводится к C.

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

Степени отношения сводимости

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

Степени любого отношения сводимости: частично заказанный отношением следующим образом. Пусть ≤ - отношение сводимости и пусть А и B быть двумя его степенями. потом А ≤ B если и только если есть набор А в А и набор B в B такой, что А ≤ B. Это эквивалентно тому свойству, что для каждого набора А в А и каждый набор B в B, А ≤ B, потому что любые два набора в А эквивалентны, и любые два множества в B эквивалентны. Обычно, как показано здесь, для обозначения степеней используются полужирные обозначения.

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

Наиболее фундаментальное понятие сводимости Сводимость по Тьюрингу. Множество А натуральных чисел Приводимый по Тьюрингу к набору B если и только если есть оракул машина Тьюринга что, когда бежать с B как его набор оракула, вычислит индикаторная функция (характеристическая функция) А. Эквивалентно, А сводится ли Тьюринг к B тогда и только тогда, когда существует алгоритм вычисления индикаторной функции для А при условии, что алгоритм снабжен средствами для правильного ответа на вопросы формы «Есть п в B?".

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

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

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

Сводимость один-один: А однозначно сводится к B если есть вычислимый индивидуальная функция ж с А(Икс) = B(ж(Икс)) для всех Икс.
Сводимость многих единиц: А сводится к B если есть вычислимая функция ж с А(Икс) = B(ж(Икс)) для всех Икс.
Сводимая таблица истинности: А сводится ли таблица истинности к B если А сводится ли Тьюринг к B с помощью единственной (оракульной) машины Тьюринга, которая производит общую функцию для каждого оракула.
Слабая сводимая таблица истинности: А сводится ли слабая таблица истинности к B если есть редукция Тьюринга от B к А и рекурсивная функция ж что ограничивает использовать. В любое время А сводится ли таблица истинности к B, А также является слабой таблицей истинности, сводимой к B, поскольку можно построить рекурсивную границу использования, учитывая максимальное использование по дереву всех оракулов, которое будет существовать, если сокращение будет полным для всех оракулов.
Положительный приводимый: А положительно сводится к B если и только если А сводится ли таблица истинности к B таким образом, чтобы можно было вычислить для каждого Икс формула, состоящая из атомов вида B(0), B(1), ... такие, что эти атомы объединены и и или, где и из а и б равно 1, если а = 1 и б = 1 и так далее.
Дизъюнктивная сводимая: подобна положительной сводимой с дополнительным ограничением, которое разрешено только или.
Конъюнктивная сводимость: аналогична положительной сводимости с дополнительным ограничением, которое разрешено только и.
Линейная сводимость: аналогична положительной сводимости, но с ограничением, что все атомы формы B(п) объединяются исключающими ИЛИ. Другими словами, А линейно сводится к B тогда и только тогда, когда вычислимая функция вычисляет для каждого Икс конечный набор F(Икс) заданный как явный список чисел, такой что Икс ∈ А если и только если F(Икс) содержит нечетное количество элементов B.

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

Ограниченные сводимости

А ограниченный вид каждой из приведенных выше сильных сводимостей может быть определен. Самые известные из них - это ограниченная редукция таблицы истинности, но есть также ограниченная таблица Тьюринга, ограниченная слабая таблица истинности и другие. Эти первые три являются наиболее распространенными и основаны на количестве запросов. Например, набор А ограниченная таблица истинности сводится к B тогда и только тогда, когда машина Тьюринга M вычисление А относительно B вычисляет список до п числа, запросы B на эти числа, а затем завершается для всех возможных ответов оракула; Значение п постоянная, не зависящая от Икс. Разница между ограниченной слабой таблицей истинности и ограниченной редукцией Тьюринга состоит в том, что в первом случае до п запросы должны выполняться одновременно, а во втором случае запросы могут выполняться один за другим. По этой причине бывают случаи, когда А ограничено по Тьюрингу, сводимое к B но не слабая таблица истинности, сводимая к B.

Сильное снижение вычислительной сложности

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

Наиболее распространенная сводимость в теории сложности вычислений - это полиномиальная сводимость; множество А полиномиально сводится к множеству B если есть функция полиномиального времени ж так что для каждого п, п в А если и только если ж(п) в B. Эта сводимость, по сути, является ограниченным по ресурсам вариантом сводимости многих единиц. Другие ограниченные по ресурсам сводимости используются в других контекстах теории сложности вычислений, где другие ограничения ресурсов представляют интерес.

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

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

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