RE (сложность)
Из Википедии, свободной энциклопедии
  (Перенаправлено из Co-RE )
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

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

.

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

.

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

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

RE-полный

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

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

  1. Проблема с остановкой : программа, получившая конечный ввод, завершает работу или будет работать вечно.
  2. По теореме Райса определение принадлежности к любому нетривиальному подмножеству множества рекурсивных функций является RE -трудным. Он будет полным всякий раз, когда набор рекурсивно перечислим.
  3. Джон Майхилл  ( 1955 ) [5] доказал, что все творческие множества являются 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. ^ Зоопарк сложности : класс co-RE
  4. ^ Цзи, Чжэнфэн; Натараджан, Ананд; Видик, Томас; Райт, Джон; Юэн, Генри (2020). "МИП*=РЕ". arXiv : 2001.04383 [ квант-ф ].
  5. ^ Майхилл, Джон (1955), «Творческие наборы», Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 1 (2): 97–108, doi : 10.1002 / malq.19550010205 , MR 0071379 .
Получено с " https://en.wikipedia.org/w/index.php?title=RE_(complexity)&oldid=1025065716 "
Contribute a better translation