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