РЕ (сложность)

В теории вычислимости и теории сложности вычислений RE ( рекурсивно перечислимые ) — это класс задач принятия решений , для которых ответ «да» может быть проверен машиной Тьюринга за конечное время. ^[1] Неформально это означает, что если ответ на экземпляр задачи — «да», то существует некоторая процедура, которая требует конечного времени для определения этого, и эта процедура никогда не выдает ложный ответ «да», когда истинный ответ — «нет». Однако, когда истинный ответ — «нет», процедура не обязательно должна останавливаться; она может войти в « бесконечный цикл » для некоторых случаев «нет». Такая процедура иногда называется полуалгоритмом , чтобы отличить ее от алгоритма , определяемого как полное решение задачи принятия решений. ^[2]

Аналогично, co-RE — это множество всех языков, которые являются дополнениями языка в RE . В некотором смысле co-RE содержит языки, принадлежность к которым может быть опровергнута за конечное время, но доказательство принадлежности может занять вечность.

Эквивалентное определение

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

Чтобы показать, что это эквивалентно, обратите внимание, что если есть машина , которая перечисляет все принятые входы, другая машина, которая принимает строку, может запуститься и принять, если строка перечисляется. И наоборот, если машина принимает, когда вход находится на языке, другая машина может перечислить все строки на языке, чередуя симуляции на каждом входе и выводя строки, которые принимаются (существует порядок выполнения, который в конечном итоге доберется до каждого шага выполнения, потому что есть счетное число упорядоченных пар входов и шагов). ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle M}$ ${\displaystyle M}$

Отношения с другими классами

Множество рекурсивных языков ( R ) является подмножеством как RE , так и co-RE . ^[3] Фактически, это пересечение этих двух классов, поскольку мы можем решить любую задачу, для которой существует распознаватель и также со-распознаватель, просто чередуя их до тех пор, пока не получим результат. Следовательно:

${\displaystyle {\mbox{R}}={\mbox{RE}}\cap {\mbox{co-RE}}}$.

Наоборот, множество языков, которые не являются ни RE , ни co-RE , известно как NRNC . Это множество языков, для которых ни членство, ни нечленство не могут быть доказаны за конечное время, и содержит все другие языки, которые не являются ни RE , ни co-RE . То есть:

${\displaystyle {\mbox{NRNC}}={\mbox{ALL}}-({\mbox{RE}}\cup {\mbox{co-RE}})}$.

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

В январе 2020 года в препринте было объявлено доказательство того, что RE эквивалентно классу MIP* (классу, в котором классический верификатор взаимодействует с несколькими всемогущими квантовыми доказывающими, которые разделяют запутанность ); ^[4] пересмотренное, но еще не полностью пересмотренное доказательство было опубликовано в Communications of the ACM в ноябре 2021 года. Доказательство подразумевает, что проблема вложения Конна и проблема Цирельсона ложны. ^[5]

RE-завершить

RE-complete — это набор задач принятия решений, которые являются полными для RE . В некотором смысле, это «самые сложные» рекурсивно перечислимые задачи. Как правило, на используемые сокращения не накладывается никаких ограничений, за исключением того, что они должны быть сокращениями типа «многие-один » .

Примеры RE-полных задач:

1. Проблема остановки : завершит ли программа выполнение при наличии конечных входных данных или будет выполняться вечно.
2. По теореме Райса , определение принадлежности к любому нетривиальному подмножеству множества рекурсивных функций является RE -трудным. Оно будет полным, если множество рекурсивно перечислимо.
3. Джон Майхилл  (1955) ^[6] доказал, что все креативные множества являются RE -полными.
4. Единая текстовая задача для групп или полугрупп . (Действительно, текстовая задача для некоторых отдельных групп является RE -полной.)
5. Определение принадлежности к общей неограниченной формальной грамматике . (Опять же, некоторые отдельные грамматики имеют проблемы принадлежности к RE -полной форме.)
6. Проблема валидности для логики первого порядка .
7. Задача на соответствие : имея список пар строк, определить, существует ли выборка из этих пар (допускающая повторы) такая, что конкатенация первых элементов (пар) равна конкатенации вторых элементов.
8. Определение того, имеет ли диофантово уравнение целочисленные решения.

co-RE-complete

co-RE-complete — это набор задач принятия решений, которые являются полными для co-RE . В некотором смысле, это дополнения к самым сложным рекурсивно перечислимым задачам.

Примеры задач co-RE-complete:

1. Задача домино для плиток Вана .
2. Проблема выполнимости для логики первого порядка .

Смотрите также

• Алгоритм завершения Кнута-Бендикса
• Список неразрешимых проблем
• Полиморфная рекурсия
• алгоритм Риша
• Полуразрешимость

Ссылки

1. Сложность зоопарка : Класс RE
2. Корфхаге, Роберт Р. (1966). Логика и алгоритмы, с приложениями к компьютерным и информационным наукам . Wiley. стр. 89. Метод решения будет называться полуалгоритмом для [задачи] P на [устройстве] M , если решение P (если оно существует) появляется после выполнения конечного числа шагов. Полуалгоритм будет называться алгоритмом, если , кроме того, всякий раз, когда задача не имеет решения, метод позволяет устройству определить его после конечного числа шагов и останавливается.
3. Сложность зоопарка : Класс co-RE
4. Цзи, Чжэнфэн; Натараджан, Ананд; Видик, Томас; Райт, Джон; Юэнь, Генри (2020). "MIP*=RE". arXiv : 2001.04383 [quant-ph].
5. Цзи, Чжэнфэн; Натараджан, Ананд; Видик, Томас; Райт, Джон; Юэнь, Генри (ноябрь 2021 г.). «MIP* = RE». Сообщения ACM . 64 (11): 131–138. doi : 10.1145/3485628 . S2CID  210165045.
6. Майхилл, Джон (1955), «Творческие множества», Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 1 (2): 97–108, doi : 10.1002/malq.19550010205, MR  0071379.