Редукция (теория вычислимости)

Чтобы узнать о других значениях, см. Сокращение (значения) .

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

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

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

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

• Рефлексивность : каждое множество сводимо к самому себе.
• Транзитив : если набор $A$ сводится к множеству $B$ и $B$ сводится к множеству $C$ затем $A$ сводится к $C$.

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

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

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

Степени любого отношения сводимости частично упорядочиваются этим отношением следующим образом. Позволять $\leq$ — отношение сводимости и пусть $C$ и $D$ быть двумя его степенями. Затем $C\leq D$ тогда и только тогда, когда существует множество $A$ в $C$ и набор $B$ в $D$ такой, что $A\leq B$. Это эквивалентно тому свойству, что для каждого множества $A$ в $C$ и каждый набор $B$ в $D$, $A\leq B$, поскольку любые два множества в C эквивалентны, а любые два множества в $D$ эквивалентны. Как показано здесь, для обозначения степеней принято использовать жирный шрифт.

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

Основная статья: Редукция Тьюринга

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

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

чем сводимость по

К сильной сводимости относятся

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

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

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

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

снижение

Основная статья: Сокращение (сложность)

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

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

чем сводимость

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

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

Внешние ссылки

• Стэнфордская энциклопедия философии: рекурсивные функции