RE (сложность)

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

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

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

• 1 Отношения с другими классами
• 2 RE-complete
• 3 co-RE-complete
• 4 См. Также
• 5 Ссылки

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

$R\; =\; RE\; \cap \; co-RE\; \{\backslash \; displaystyle\; \{\backslash \; t\_dv\; \{R\}\}\; =\; \{\backslash \; t\_dv\; \{RE\}\}\; \backslash \; cap\; \{\backslash \; t\_dv\; \{co-RE\}\}\}$.

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

$NRNC\; =\; ALL\; -\; (RE\; \cup \; co-RE)\; \{\backslash \; displaystyle\; \{\backslash \; t\_dv\; \{NRNC\}\}\; =\; \{\backslash \; t\_dv\; \{ALL\}\}\; -\; (\{\backslash \; t\_dv\; \{RE\}\}\; \backslash \; cup\; \{\backslash \; t\_dv\; \{\; co-RE\}\})\}$.

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

В январе 2020 года в препринте объявлено доказательство того, что RE эквивалентен классу MIP * (класс, в котором классический верификатор взаимодействует с несколькими всемогущими квантовые доказывающие, которые разделяют запутанность).

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

Примеры проблем с повторным завершением:

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

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

Примеры задач совместного RE-завершения:

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

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

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