Сводимость и степени неразрешимости

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

Definition

Задача сводится к другой, когда алгоритм, имеющий доступ к решателю для второй задачи, может решить первую; задачи, которые сводятся друг к другу, имеют общую степень неразрешимости, и эти степени образуют упорядоченность, измеряющую относительную алгоритмическую сложность.

Scope

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

Core questions

• Как мы можем сказать, что одна неразрешимая задача сложнее другой?
• Как редукции используются как для доказательства неразрешимости, так и для организации задач?
• Что порождает скачок Тьюринга и почему он всегда строго сложнее?
• Существуют ли задачи, строго находящиеся между разрешимыми и проблемой остановки?

Key theories

Сводимость и скачок Тьюринга

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

Существование промежуточных степеней

Теорема Фридберга-Мучника решила проблему Поста, построив вычислимо перечислимые задачи, которые неразрешимы, но строго проще проблемы остановки, используя метод приоритета, что показало богатую структуру степеней.

Clinical relevance

Метод редукции является повседневным инструментом для доказательства неразрешимости задач или, в теории сложности, их неразрешимости за полиномиальное время (intractability): демонстрация того, что известная сложная задача сводится к новой, переносит сложность, что является именно тем, как устанавливаются результаты о неразрешимости и NP-полноте в математике и информатике.

History

Тьюринг ввел понятие оракульных машин в 1939 году, а Пост в 1944 году сформулировал исследование степеней неразрешимости и поставил проблему существования промежуточных вычислимо перечислимых степеней. Фридберг и Мучник независимо решили ее в 1956–1957 годах, изобретя метод приоритета, который стал центральным методом в этой области.

Key figures

• Emil Post
• Alan Turing
• Richard Friedberg
• Albert Muchnik

Seminal works

• soare2016
• rogers1987

Frequently asked questions

Что такое редукция, интуитивно?

Это способ решения одной задачи с использованием решателя для другой. Если вы можете преобразовать любой экземпляр задачи A в экземпляр задачи B так, чтобы ответы совпадали, то B по крайней мере так же сложна, как A, и решение B дает решение A.

Существуют ли задачи сложнее проблемы остановки?

Да, бесконечно много. Применение скачка Тьюринга к проблеме остановки дает строго более сложную задачу, а повторение операции строит бесконечную иерархию, так что неразрешимость имеет неограниченные степени, а не один уровень.