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

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

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

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

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

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

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

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

{\mbox{R}}={\mbox{RE}}\cap {\mbox{co-RE}}

.

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

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

.

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

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

RE-полный

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

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

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

совместное RE-завершение

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

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

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

См. также

Ссылки

^ Зоопарк сложности : Класс RE
^ Корфхаге, Роберт Р. (1966). Логика и алгоритмы с приложениями к компьютерным и информационным наукам . Уайли. п. 89 . Метод решения будем называть полуалгоритмом для [задачи] P на [устройстве] M , если решение P (если оно существует) появляется после выполнения конечного числа шагов. Полуалгоритм будем называть алгоритмом, если , кроме того, всякий раз, когда задача не имеет решения, метод позволяет устройству определить это после конечного числа шагов и остановок.
^ Зоопарк сложности : Класс co-RE
^ Цзи, Чжэнфэн; Натараджан, Ананд; Видик, Томас; Райт, Джон; Юэнь, Генри (2020). «МИП*=РЕ». arXiv : 2001.04383 [ квант-ph ].
^ Цзи, Чжэнфэн; Натараджан, Ананд; Видик, Томас; Райт, Джон; Юэнь, Генри (ноябрь 2021 г.). «МИП* = РЕ» . Коммуникации АКМ . 64 (11): 131–138. дои : 10.1145/3485628 . S2CID 210165045 .
^ Майхилл, Джон (1955), «Творческие множества», Журнал математической логики и основ математики , 1 (2): 97–108, doi : 10.1002/malq.19550010205 , MR 0071379 .

[1] Зоопарк сложности : Класс RE

[2] Корфхаге, Роберт Р. (1966). Логика и алгоритмы с приложениями к компьютерным и информационным наукам . Уайли. п. 89 . Метод решения будем называть полуалгоритмом для [задачи] P на [устройстве] M , если решение P (если оно существует) появляется после выполнения конечного числа шагов. Полуалгоритм будем называть алгоритмом, если , кроме того, всякий раз, когда задача не имеет решения, метод позволяет устройству определить это после конечного числа шагов и остановок.

[3] Зоопарк сложности : Класс co-RE

[4] Цзи, Чжэнфэн; Натараджан, Ананд; Видик, Томас; Райт, Джон; Юэнь, Генри (2020). «МИП*=РЕ». arXiv : 2001.04383 [ квант-ph ].

[5] Цзи, Чжэнфэн; Натараджан, Ананд; Видик, Томас; Райт, Джон; Юэнь, Генри (ноябрь 2021 г.). «МИП* = РЕ» . Коммуникации АКМ . 64 (11): 131–138. дои : 10.1145/3485628 . S2CID 210165045 .

[6] Майхилл, Джон (1955), «Творческие множества», Журнал математической логики и основ математики , 1 (2): 97–108, doi : 10.1002/malq.19550010205 , MR 0071379 .

[1]

[2]

[3]

[4]

[5]

[6]

v т и Классы сложности
Считается возможным	ДЛОГТАЙМ переменного тока ⁰ АСС ⁰ ТК ⁰ л СЛ РЛ Флорида Нидерланды NL-полный Северная Каролина СК СС П P-полный ЗПП РП БПП Министерство национальной обороны АПХ ФП
Подозрение неосуществимое	ВВЕРХ НАПРИМЕР NP-полный NP-жесткий со-НП со-NP-полный ТФНП ФНП ЯВЛЯЮСЬ КМА PH ⊕P ПП #П #P-полное ИП PSPACE PSPACE-полный
Считается невозможным	ВРЕМЯ ЭКСПРЕСС СЛЕДУЮЩЕЕ ВРЕМЯ EXPSPACE 2-ВРЕМЯ ЭКСПЛУАТАЦИИ ЭЛЕМЕНТАРНЫЙ пиар Р РЭ ВСЕ
Иерархии классов	Полиномиальная иерархия Экспоненциальная иерархия Иерарх Гжегорчик Арифметическая иерархия Булева иерархия
Семьи классов	DTIME NTIME ДСПЕЙС НСПАСЕ Вероятностно проверяемое доказательство Интерактивная система доказательств
Список классов сложности