Войти
В теории вычислимости многие отношения сводимости (также называемые редукциями, сводимостью и понятиями сводимости ) изучаются. Они мотивированы вопросом: можно ли при заданных наборах натуральных чисел A и B эффективно преобразовать метод определения принадлежности к B в метод определения принадлежности к A? Если ответ на этот вопрос утвердительный, то говорят, что A сводится к B.
Изучение понятий сводимости мотивировано изучением проблем принятия решений. Для многих понятий сводимости, если любое невычислимое множество сводится к множеству A, то A также должно быть невычислимым. Это дает мощный метод доказательства невычислимости многих множеств.
A отношение сводимости - это бинарное отношение на множествах натуральных чисел, которое является
Эти два свойства подразумевают, что сводимость - это a предварительный заказ на множестве натуральных чисел. Однако не все предзаказы рассматриваются как понятия сводимости. Понятия, изучаемые в теории вычислимости, обладают тем неформальным свойством, что A сводится к B тогда и только тогда, когда любая (возможно, неэффективная) процедура принятия решения для B может быть эффективно преобразована в процедуру принятия решения для A. Различные соотношения сводимости различаются в зависимости от методов, которые они допускают. такой процесс преобразования использовать.
Каждое отношение сводимости (фактически, каждый предпорядок) индуцирует отношение эквивалентности на множестве степеней натуральных чисел, в котором два набора эквивалентны тогда и только тогда, когда каждое из них сводится к другому. В теории рекурсии эти классы эквивалентности называются степенями отношения сводимости. Например, степени Тьюринга - это классы эквивалентности множеств натуральных чисел, индуцированные сводимостью по Тьюрингу.
Степени любого отношения сводимости частично упорядочиваются отношением следующим образом. Пусть ≤ - отношение сводимости, и пусть A и B - две его степени. Тогда A≤ Bтогда и только тогда, когда существует множество A в A и множество B в B такое, что A ≤ B. Это эквивалентно тому свойству, что для каждого набора A в A и каждый набор B в B, A ≤ B, потому что любые два набора в A эквивалентны, а любые два набора в B эквивалентны. Обычно, как показано здесь, для обозначения степеней используются полужирные обозначения.
Самым фундаментальным понятием сводимости является сводимость по Тьюрингу. Множество натуральных чисел A сводимо по Тьюрингу к множеству B тогда и только тогда, когда существует машина Тьюринга, которая при запуске с B в качестве своего набора оракулов будет вычислять индикаторная функция (характеристическая функция) A. Эквивалентно, A сводится по Тьюрингу к B тогда и только тогда, когда существует алгоритм для вычисления индикаторной функции для A при условии, что алгоритм снабжен средствами для правильного ответа на вопросы формы «Находится ли в Б?».
Сводимость по Тьюрингу служит разделительной чертой для других понятий сводимости, потому что, согласно тезису Чёрча-Тьюринга, это наиболее общее отношение сводимости, которое эффективно. Отношения сводимости, которые подразумевают сводимость по Тьюрингу, стали известны как сильная сводимость, в то время как те, которые подразумеваются сводимостью по Тьюрингу, являются слабой сводимостью. Эквивалентно сильное отношение сводимости - это отношение, степени которого образуют отношение эквивалентности более тонкое, чем степени Тьюринга, тогда как отношение слабой сводимости - это отношение, степени которого образуют более грубое отношение эквивалентности, чем эквивалентность Тьюринга.
Сильные сводимости включают
Многие из них были введены Постом (1944). Сообщение искало не- рекурсивный, рекурсивно перечислимый набор, к которому не могла быть сведена проблема остановки по Тьюрингу. Поскольку в 1944 году он не смог построить такое множество, он вместо этого работал над аналогичными проблемами для различных введенных им сводимостей. Эти сводимости с тех пор стали предметом многих исследований, и между ними известно множество взаимосвязей.
A ограниченная форма каждой из вышеупомянутых сильных сводимостей может быть определена. Наиболее известные из них - это ограниченная редукция таблицы истинности, но есть также ограниченная таблица Тьюринга, ограниченная слабая таблица истинности и другие. Эти первые три являются наиболее распространенными и основываются на количестве запросов. Например, множество A является ограниченной таблицей истинности, сводимой к B тогда и только тогда, когда машина Тьюринга M, вычисляющая A относительно B, вычисляет список до n чисел, запрашивает B по этим числам и затем завершает работу для всех возможных ответов оракула; значение n является константой, не зависящей от x. Разница между ограниченной слабой таблицей истинности и ограниченной редукцией по Тьюрингу заключается в том, что в первом случае до n запросов должны выполняться одновременно, в то время как во втором случае запросы могут выполняться один за другим. По этой причине бывают случаи, когда A ограничено, сводимое по Тьюрингу к B, но не слабая таблица истинности, сводимая к B.
Сильное сокращение, перечисленное выше, ограничивает способ в котором информация оракула может быть доступна с помощью процедуры принятия решения, но не ограничивает иным образом доступные вычислительные ресурсы. Таким образом, если множество A разрешимо, то оно сводится к любому множеству B при любом из отношений сильной сводимости, перечисленных выше, даже если A не разрешимо за полиномиальное или экспоненциальное время. Это приемлемо при изучении теории рекурсии, которая интересуется теоретической вычислимостью, но нецелесообразно для теории сложности вычислений, изучающей, какие множества могут быть решены при определенных асимптотических ограничениях ресурсов.
Наиболее распространенная сводимость в теории сложности вычислений - это сводимость за полиномиальное время ; множество A сводимо за полиномиальное время к множеству B, если существует функция f за полиномиальное время, такая что для каждого n, n находится в A тогда и только тогда, когда f (n) находится в B. Эта сводимость, по сути, является a ограниченная ресурсами версия сводимости многих единиц. Другие ограниченные по ресурсам сводимости используются в других контекстах теории сложности вычислений, где другие ограничения ресурсов представляют интерес.
Хотя сводимость по Тьюрингу является наиболее общей эффективной сводимостью, обычно изучаются более слабые отношения сводимости. Эти сводимости связаны с относительной определимостью множеств над арифметикой или теорией множеств. К ним относятся:
, n-й скачок Тьюринга B для некоторого натурального числа n. Арифметическая иерархия дает более тонкую классификацию арифметической сводимости.
определимо (см. аналитическая иерархия ) над стандартной моделью арифметики Пеано с предикатом для B. Эквивалентно, A гиперарифметичен в B тогда и только тогда, когда A сводится по Тьюрингу к 
, α-й скачок Тьюринга для B, для некоторых B- рекурсивный порядковый номер α.