Проблема почтовой корреспонденции является неразрешимой проблемой , решения , которое было введено Эмилем сообщением в 1946 году [1] Так как это проще , чем проблемы остановки и проблема разрешения он часто используется в доказательствах неразрешимости.
Определение проблемы
Позволять быть алфавитом не менее чем из двух символов. Вход задачи состоит из двух конечных списков а также слов над . Решение этой проблемы - последовательность индексов с участием а также для всех , так что
Тогда проблема решения состоит в том, чтобы решить, существует ли такое решение или нет.
Альтернативное определение
Это приводит к эквивалентному альтернативному определению, часто встречающемуся в литературе, согласно которому любые два гомоморфизма с общим доменом и общим кодоменом образуют экземпляр проблемы корреспонденции Post, которая теперь спрашивает, существует ли непустое слово в такой области, что
- .
Другое определение легко описывает эту проблему как разновидность головоломки. Мы начинаем с набора домино, каждая из которых содержит две струны, по одной с каждой стороны. Индивидуальное домино выглядит как
и коллекция домино выглядит как
- .
Задача состоит в том, чтобы составить список этих домино (повторение разрешено) так, чтобы строка, которую мы получаем, считывая символы вверху, была такой же, как и строка символов внизу. Этот список называется совпадением. Задача почтовой переписки - определить, есть ли совпадения в коллекции домино. Например, следующий список подходит для этой головоломки.
- .
Для некоторых коллекций домино найти совпадение может быть невозможно. Например, коллекция
- .
не может содержать совпадение, потому что каждая верхняя строка длиннее соответствующей нижней строки.
Примеры проблем
Пример 1
Рассмотрим следующие два списка:
|
|
Решением этой проблемы будет последовательность (3, 2, 3, 1), потому что
Кроме того, поскольку (3, 2, 3, 1) является решением, поэтому все его «повторения», такие как (3, 2, 3, 1, 3, 2, 3, 1) и т.д .; то есть, когда решение существует, существует бесконечно много таких повторяющихся решений.
Однако если бы эти два списка состояли только из а также из этих наборов, тогда не было бы никакого решения (последняя буква любой такой строки α не совпадает с буквой перед ней, тогда как β создает только пары одной и той же буквы).
Удобный способ просмотра экземпляра задачи почтовой корреспонденции - это набор блоков формы
|
существует неограниченное количество блоков каждого типа. Таким образом, приведенный выше пример рассматривается как
я = 1 |
я = 2 |
я = 3 |
где у решателя есть бесконечный запас каждого из этих трех типов блоков. Решение соответствует некоторому способу укладки блоков рядом друг с другом так, чтобы строка в верхних ячейках соответствовала строке в нижних ячейках. Тогда решение в приведенном выше примере соответствует:
я 1 = 3 |
я 2 = 2 |
я 3 = 3 |
я 4 = 1 |
Пример 2
Снова используя блоки для представления экземпляра проблемы, ниже приведен пример, который имеет бесконечно много решений в дополнение к типу, полученному путем простого «повторения» решения.
1 |
2 |
3 |
В этом случае каждая последовательность вида (1, 2, 2, ..., 2, 3) является решением (в дополнение ко всем их повторениям):
1 |
2 |
2 |
2 |
3 |
Схема доказательства неразрешимости
Наиболее распространенное доказательство неразрешимости PCP описывает экземпляр PCP, который может моделировать вычисление произвольной машины Тьюринга на конкретном входе. Соответствие произойдет тогда и только тогда, когда ввод будет принят машиной Тьюринга. Поскольку решение о том, примет ли машина Тьюринга входные данные, является основной неразрешимой проблемой , PCP также не может быть разрешимым. Следующее обсуждение основано на учебнике Майкла Сипсера « Введение в теорию вычислений» . [2]
Более подробно, идея состоит в том, что строка вверху и внизу будет историей вычислений машины Тьюринга. Это означает, что он будет перечислять строку, описывающую начальное состояние, за которой следует строка, описывающая следующее состояние, и так далее, пока она не закончится строкой, описывающей принимающее состояние. Строки состояния разделяются некоторым символом-разделителем (обычно пишется #). Согласно определению машины Тьюринга, полное состояние машины состоит из трех частей:
- Текущее содержимое ленты.
- Текущее состояние конечного автомата, который управляет головкой ленты.
- Текущее положение головки на ленте.
Хотя на ленте бесконечно много ячеек, только некоторый конечный префикс из них будет непустым. Мы записываем это как часть нашего состояния. Чтобы описать состояние конечного управления, мы создаем новые символы с обозначениями от q 1 до q k для каждого из k состояний конечного автомата . Мы вставляем правильный символ в строку, описывающую содержимое ленты в позиции головки ленты, тем самым указывая как положение головки ленты, так и текущее состояние конечного элемента управления. Для алфавита {0,1} типичное состояние может выглядеть примерно так:
101101110 q 7 00110.
Тогда простая история вычислений будет выглядеть примерно так:
q 0 101 # 1 q 4 01 # 11 q 2 1 # 1 q 8 10.
Мы начинаем с этого блока, где x - это входная строка, а q 0 - начальное состояние:
q 0 x # |
Верх начинает «отставать» от низа на одно состояние и сохраняет это отставание до самого конца этапа. Затем для каждого символа a в алфавите ленты, а также символа #, у нас есть блок «copy», который копирует его без изменений из одного состояния в другое:
а |
а |
У нас также есть блок для каждого перехода положения, который может сделать машина, показывающий, как движется головка ленты, как изменяется конечное состояние и что происходит с окружающими символами. Например, здесь головка ленты находится над 0 в состоянии 4, а затем записывает 1 и перемещается вправо, переходя в состояние 7:
q 4 0 |
1 квартал 7 |
Наконец, когда верх достигает состояния принятия, нижнему нужен шанс, наконец, догнать, чтобы завершить матч. Чтобы разрешить это, мы расширяем вычисление так, чтобы при достижении состояния приема каждый последующий машинный шаг приводил к исчезновению символа рядом с головкой ленты, по одному, до тех пор, пока не осталось ни одного символа. Если q f - состояние приема, мы можем представить это с помощью следующих блоков перехода, где a - символ ленточного алфавита:
|
|
Необходимо проработать ряд деталей, таких как работа с границами между состояниями, обеспечение того, чтобы наша исходная плитка была первой в матче, и так далее, но это показывает общую идею того, как статическая головоломка может имитировать тьюринговую машинные вычисления.
Предыдущий пример
q 0 101 # 1 q 4 01 # 11 q 2 1 # 1 q 8 10.
представляет собой следующее решение проблемы почтовой корреспонденции:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ... |
Варианты
Было рассмотрено множество вариантов PCP. Одна из причин состоит в том, что, когда кто-то пытается доказать неразрешимость какой-либо новой проблемы путем редукции из PCP, часто случается, что первое обнаруженное сокращение происходит не из самого PCP, а из явно более слабой версии.
- Проблема может быть сформулирована в терминах морфизмов моноидов f , g из свободного моноида B ∗ в свободный моноид A ∗, где B имеет размер n . Проблема состоит в том, чтобы определить, существует ли слово w в B + такое, что f ( w ) = g ( w ). [3]
- Условие того, что алфавит иметь не менее двух символов, так как проблема разрешима, если имеет только один символ.
- Простой вариант - зафиксировать n - количество плиток. Эта проблема разрешима, если n ≤ 2, [4], но остается неразрешимой при n ≥ 5. Неизвестно, разрешима ли проблема для 3 ≤ n ≤ 4. [5]
- Задача круговой корреспонденции Post спрашивает, можно найти так, что а также являются сопряженными словами , т. е. равны по модулю вращения. Этот вариант неразрешим. [6]
- Одним из наиболее важных вариантов PCP является проблема ограниченного соответствия Post , которая спрашивает, можем ли мы найти совпадение, используя не более k плиток, включая повторяющиеся плитки. Поиск методом грубой силы решает проблему за время O (2 k ), но это может быть трудно улучшить, поскольку проблема является NP-полной . [7] В отличие от некоторых NP-полных задач, таких как проблема логической выполнимости , небольшая вариация ограниченной задачи также оказалась полной для RNP, что означает, что она остается сложной, даже если входные данные выбираются случайным образом (это сложно среднее по равномерно распределенным входам). [8]
- Другой вариант PCP называется отмеченной проблемой почтовой корреспонденции , в которой каждый должен начинаться с другого символа, и каждый также должен начинаться с другого символа. Халава, Хирвенсало и де Вольф показали, что эта вариация разрешима за экспоненциальное время . Более того, они показали, что если это требование немного ослабить, так что только один из первых двух символов должен отличаться (так называемая проблема почтовой корреспонденции с двумя пометками), проблема снова становится неразрешимой. [9]
- Проблема пост-встраивания - это еще один вариант, когда ищут индексы. такой, что является (рассеянной) подслово из. Этот вариант легко разрешим, поскольку, когда существуют некоторые решения, в частности, существует решение длины один. Более интересна задача встраивания регулярных сообщений , еще один вариант, в котором ищутся решения, принадлежащие данному регулярному языку (представленные, например, в форме регулярного выражения на множестве). Проблема регулярного пост-вложения все еще разрешима, но из-за добавленного регулярного ограничения она имеет очень высокую сложность, которая доминирует над каждой многократно рекурсивной функцией. [10]
- Задача соответствия идентичности (ICP) спрашивает, может ли конечный набор пар слов (над групповым алфавитом) сгенерировать идентичную пару последовательностью конкатенаций. Проблема неразрешима и эквивалентна следующей групповой проблеме: является ли полугруппа, порожденная конечным набором пар слов (над групповым алфавитом) группой. [11]
Рекомендации
- ^ Сообщение EL (1946). «Вариант рекурсивно неразрешимой задачи» (PDF) . Бык. Амер. Математика. Soc . 52 (4): 264–269. DOI : 10,1090 / s0002-9904-1946-08555-9 .
- ^ Майкл Сипсер (2005). «Простая неразрешимая проблема». Введение в теорию вычислений (2-е изд.). Thomson Course Technology. С. 199–205. ISBN 0-534-95097-3.
- ^ Саломаа, Арто (1981). Драгоценности теории формального языка . Pitman Publishing. С. 74–75. ISBN 0-273-08522-0. Zbl 0487.68064 .
- ^ Эренфойхт, А .; Karhumäki, J .; Розенберг, Г. (ноябрь 1982 г.). «(Обобщенная) проблема почтовой корреспонденции со списками, состоящими из двух слов, разрешима» . Теоретическая информатика . 21 (2): 119–144. DOI : 10.1016 / 0304-3975 (89) 90080-7 .
- ^ Т. Нери (2015). «Неразрешимость в двоичных системах тегов и проблема пост-соответствия для пяти пар слов» . В Эрнст В. Майр и Николас Оллингер (ред.). 32-й Международный симпозиум по теоретическим аспектам информатики (STACS 2015) . STACS 2015. 30 . Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. С. 649–661. DOI : 10,4230 / LIPIcs.STACS.2015.649 .
- ^ К. Руохонен (1983). «О некоторых вариантах переписки Поста». Acta Informatica . Springer. 19 (4): 357–367. DOI : 10.1007 / BF00290732 . S2CID 20637902 .
- ^ Майкл Р. Гэри ; Дэвид С. Джонсон (1979). Компьютеры и непоколебимость: руководство по теории NP-полноты . WH Freeman. п. 228 . ISBN 0-7167-1045-5.
- ^ Ю. Гуревич (1991). «Средняя полнота дела» (PDF) . J. Comp. Sys. Sci . Elsevier Science. 42 (3): 346–398. DOI : 10.1016 / 0022-0000 (91) 90007-R . ЛВП : 2027,42 / 29307 .
- ^ В. Халава; М. Хирвенсало; Р. де Вольф (2001). «Отмеченный PCP разрешимый». Теор. Comput. Sci . Elsevier Science. 255 (1-2): 193-204. DOI : 10.1016 / S0304-3975 (99) 00163-2 .
- ^ П. Шамбар; Ph. Schnoebelen (2007). «Проблема пост-внедрения не является примитивно рекурсивной, с приложениями к системам каналов» (PDF) . Конспект лекций по информатике. 4855 . Springer: 265–276. DOI : 10.1007 / 978-3-540-77050-3_22 . ISBN 978-3-540-77049-7. Цитировать журнал требует
|journal=
( помощь ) - ^ Пол С. Белл; Игорь Потапов (2010). «О неразрешимости проблемы тождественного соответствия и ее приложениях для словесных и матричных полугрупп». Международный журнал основ информатики . World Scientific. 21 (6): 963–978. arXiv : 0902.1975 . DOI : 10.1142 / S0129054110007660 .
Внешние ссылки
- Эйтан М. Гурари. Введение в теорию вычислений , глава 4, проблема соответствия Поста . Доказательство неразрешимости PCP на основе грамматик Хомского типа 0 .
- Донг, Цзин. «Анализ и решение экземпляра PCP». 2012 Национальная конференция по информационным технологиям и компьютерным наукам. В документе описывается эвристическое правило для решения некоторых конкретных случаев PCP.
- Онлайн-программа для решения PCP на основе PHP
- PCP НА ДОМУ
- PCP - приятная проблема
- Решатель PCP на Java