Проблема с почтовой перепиской - Post correspondence problem

В Проблема с почтовой перепиской является неразрешимый проблема решения это было введено Эмиль Пост в 1946 г.^[1] Потому что это проще, чем проблема остановки и Entscheidungsproblem он часто используется в доказательствах неразрешимости.

Определение проблемы

Позволять ${ displaystyle A}$ быть алфавитом не менее чем из двух символов. Вход задачи состоит из двух конечных списков ${ displaystyle alpha _ {1}, ldots, alpha _ {N}}$ и ${ displaystyle beta _ {1}, ldots, beta _ {N}}$ слов над ${ displaystyle A}$ . Решение этой проблемы - последовательность индексов ${ Displaystyle (я_ {к}) _ {1 leq k leq K}}$ с участием ${ displaystyle K geq 1}$ и ${ displaystyle 1 leq i_ {k} leq N}$ для всех ${ displaystyle k}$ , так что

{ displaystyle alpha _ {i_ {1}} ldots alpha _ {i_ {K}} = beta _ {i_ {1}} ldots beta _ {i_ {K}}.}

Тогда проблема решения состоит в том, чтобы решить, существует ли такое решение или нет.

Альтернативное определение

{ displaystyle g: (i_ {1}, ldots, i_ {K}) mapsto alpha _ {i_ {1}} ldots alpha _ {i_ {K}}}

{ displaystyle h: (i_ {1}, ldots, i_ {K}) mapsto beta _ {i_ {1}} ldots beta _ {i_ {K}}.}

Это приводит к эквивалентному альтернативному определению, часто встречающемуся в литературе, согласно которому любые два гомоморфизма ${ displaystyle g, h}$ с общим доменом и общим кодоменом образуют экземпляр проблемы корреспонденции Post, которая теперь спрашивает, существует ли непустое слово ${ displaystyle w}$ в такой области, что

{ Displaystyle г (ш) = ч (ш)}

.

Другое определение легко описывает эту проблему как разновидность головоломки. Мы начинаем с коллекции домино, каждая из которых состоит из двух струн, по одной с каждой стороны. Индивидуальное домино выглядит как

{ displaystyle [a / ab]}

и коллекция домино выглядит как

{ displaystyle {[bc / ca], [a / ab], [ca / a], [abc / c]}}

.

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

{ displaystyle {[a / ab], [bc / ca], [a / ab], [abc / c]}}

.

Для некоторых коллекций домино найти совпадение может быть невозможно. Например, коллекция

{ displaystyle {[abc / ab], [ca / a], [acc / ba]}}

.

не может содержать совпадений, потому что каждая верхняя строка длиннее соответствующей нижней строки.

Примеры проблемы

Пример 1

Рассмотрим следующие два списка:

α₁	α₂	α₃
а	ab	bba

β₁	β₂	β₃
баа	аа	bb

Решением этой проблемы будет последовательность (3, 2, 3, 1), потому что

{ Displaystyle альфа _ {3} альфа _ {2} альфа _ {3} альфа _ {1} = bba cdot ab cdot bba cdot a = bbaabbbaa = bb cdot aa cdot bb cdot baa = beta _ {3} beta _ {2} beta _ {3} beta _ {1}.}

Кроме того, поскольку (3, 2, 3, 1) является решением, поэтому все его «повторения», такие как (3, 2, 3, 1, 3, 2, 3, 1) и т.д .; то есть, когда решение существует, существует бесконечно много таких повторяющихся решений.

Однако если бы два списка состояли только из ${ displaystyle alpha _ {2}, alpha _ {3}}$ и ${ displaystyle beta _ {2}, beta _ {3}}$ из этих наборов, тогда не было бы решения (последняя буква любой такой строки α не совпадает с буквой перед ней, тогда как β создает только пары одинаковых букв).

Удобный способ просмотра экземпляра задачи почтовой корреспонденции - это набор блоков формы

α_я
β_я

существует неограниченное количество блоков каждого типа. Таким образом, приведенный выше пример рассматривается как

а
баа

я = 1

ab
аа

я = 2

bba
bb

я = 3

где у решателя есть бесконечный запас каждого из этих трех типов блоков. Решение соответствует некоторому способу укладки блоков рядом друг с другом таким образом, чтобы строка в верхних ячейках соответствовала строке в нижних ячейках. Тогда решение в приведенном выше примере соответствует:

bba
bb

я₁ = 3

ab
аа

я₂ = 2

bba
bb

я₃ = 3

а
баа

я₄ = 1

Пример 2

Снова используя блоки для представления экземпляра проблемы, ниже приводится пример, который имеет бесконечно много решений в дополнение к типу, полученному простым «повторением» решения.

bb
б

1

ab
ба

2

c
до н.э

3

В этом случае каждая последовательность вида (1, 2, 2, ..., 2, 3) является решением (в дополнение ко всем их повторениям):

bb
б

1

ab
ба

2

ab
ба

2

ab
ба

2

c
до н.э

3

Схема доказательства неразрешимости

Наиболее распространенное доказательство неразрешимости PCP описывает экземпляр PCP, который может моделировать вычисление произвольного Машина Тьюринга на конкретном входе. Соответствие произойдет тогда и только тогда, когда ввод будет принят машиной Тьюринга. Потому что решить, примет ли машина Тьюринга входные данные, является основной неразрешимой проблемой., PCP также не может быть разрешимым. Следующее обсуждение основано на Майкл Сипсер учебник Введение в теорию вычислений.^[2]

Если говорить более подробно, идея состоит в том, что нить сверху и снизу будет история вычислений вычисления машины Тьюринга. Это означает, что он будет перечислять строку, описывающую начальное состояние, за которой следует строка, описывающая следующее состояние, и так далее, пока она не закончится строкой, описывающей принимающее состояние. Строки состояния разделяются некоторым символом-разделителем (обычно пишется #). Согласно определению машины Тьюринга, полное состояние машины состоит из трех частей:

Текущее содержимое ленты.
Текущее состояние конечный автомат который управляет головкой ленты.
Текущее положение головки на ленте.

Хотя на ленте бесконечно много ячеек, только некоторый конечный префикс из них будет непустым. Мы записываем это как часть нашего состояния. Для описания состояния конечного управления мы создаем новые символы, помеченные q₁ через q_k, для каждого конечного автомата k состояния. Мы вставляем правильный символ в строку, описывающую содержимое ленты в положении головки ленты, тем самым указывая как положение головки ленты, так и текущее состояние конечного элемента управления. Для алфавита {0,1} типичное состояние может выглядеть примерно так:

101101110q₇00110.

Тогда простая история вычислений будет выглядеть примерно так:

q₀101#1q₄01#11q₂1#1q₈10.

Начнем с этого блока, где Икс это входная строка и q₀ это начальное состояние:


q₀Икс#

Верх начинает «отставать» от низа на одно состояние и сохраняет это отставание до самого конца этапа. Далее для каждого символа а в ленточном алфавите, а также #, у нас есть блок «копия», который копирует его без изменений из одного состояния в другое:

а
а

У нас также есть блок для каждого перехода положения, который может сделать машина, показывающий, как движется головка ленты, как изменяется конечное состояние и что происходит с окружающими символами. Например, здесь головка ленты находится над 0 в состоянии 4, а затем записывает 1 и перемещается вправо, переходя в состояние 7:

q₄0
1q₇

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

q_жа
q_ж

водный_ж
q_ж

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

Предыдущий пример

q₀101#1q₄01#11q₂1#1q₈10.

представляет собой следующее решение проблемы почтовой корреспонденции:


q₀101#

q₀1
1 q₄

0
0

1
1

#
#

1
1

q₄ 0
1 q₂

1
1

#
#

1
1

1 q₂1
q₈10

#
#

1 q₈
q₈

1
1

0
0

#
#

q₈ 1
q₈

0
0

#
#

q₈ 0
q₈

#
#

q₈

#
#

...

Варианты

Было рассмотрено множество вариантов PCP. Одна из причин заключается в том, что, когда кто-то пытается доказать неразрешимость какой-либо новой проблемы путем редукции из PCP, часто случается, что первое обнаруженное сокращение происходит не из самого PCP, а из явно более слабой версии. Также обратите внимание, что если удалить переписка, то проблема становится разрешимой.

Проблема может быть сформулирована в терминах моноидные морфизмы ж, г из бесплатного моноида B^∗ в свободный моноид А^∗ где B имеет размер п. Проблема в том, чтобы определить, есть ли слово ш в B⁺ такой, что ж(ш) = г(ш).^[3]
Условие того, что алфавит ${ displaystyle A}$ иметь хотя бы два символа, так как проблема разрешима, если ${ displaystyle A}$ имеет только один символ.
Простой вариант - исправить п, количество плиток. Эта проблема разрешима, если п ≤ 2,^[4] но остается неразрешимым для п ≥ 5. Неизвестно, разрешима ли задача при 3 ≤ п ≤ 4.^[5]
В круговой Проблема с почтовой перепиской спрашивает, индексы ${ Displaystyle i_ {1}, i_ {2}, ldots}$ можно найти так, что ${ Displaystyle альфа _ {я_ {1}} cdots альфа _ {я_ {к}}}$ и ${ displaystyle beta _ {i_ {1}} cdots beta _ {i_ {k}}}$ находятся сопряженные слова, т.е. они равны по модулю вращения. Этот вариант неразрешим.^[6]
Одним из наиболее важных вариантов PCP является ограниченный Проблема с почтовой перепиской, который спрашивает, можем ли мы найти совпадение, используя не более k плитки, включая повторяющиеся плитки. Перебор методом перебора решает задачу за время O (2^k), но это может быть трудно улучшить, поскольку проблема НП-полный.^[7] В отличие от некоторых NP-полных задач, таких как проблема логической выполнимости, также было показано, что небольшая вариация ограниченной задачи является полной для RNP, что означает, что она остается сложной, даже если входы выбираются случайным образом (это сложно в среднем для равномерно распределенных входов).^[8]
Другой вариант PCP называется отмечен Проблема с почтовой корреспонденцией, в котором каждый ${ displaystyle alpha _ {я}}$ должен начинаться с другого символа, и каждый ${ displaystyle beta _ {я}}$ также должен начинаться с другого символа. Халава, Хирвенсало и де Вольф показали, что эта вариация разрешима в экспоненциальное время. Более того, они показали, что если это требование немного ослабить, так что только один из первых двух символов должен отличаться (так называемая проблема почтовой корреспонденции с двумя пометками), проблема снова становится неразрешимой.^[9]
В Пост-встраивание проблемы это еще один вариант поиска индексов ${ displaystyle i_ {1}, i_ {2}, ldots}$ такой, что ${ Displaystyle альфа _ {я_ {1}} cdots альфа _ {я_ {к}}}$ это (разбросанное) подслово из ${ displaystyle beta _ {i_ {1}} cdots beta _ {i_ {k}}}$ . Этот вариант легко разрешим, поскольку, когда существуют некоторые решения, в частности, существует решение длины один. Более интересным является Обычный Пост-встраивание проблемы, еще один вариант, в котором ищутся решения, принадлежащие данному регулярному языку (представленные, например, в форме регулярного выражения на множестве ${ Displaystyle {1, ldots, N }}$ ). Проблема регулярного пост-вложения все еще разрешима, но из-за добавленного регулярного ограничения она имеет очень высокую сложность, которая доминирует над каждой многократно рекурсивной функцией.^[10]
В Проблема соответствия идентичности (ICP) спрашивает, может ли конечный набор пар слов (по групповому алфавиту) сгенерировать идентичную пару с помощью последовательности конкатенаций. Проблема неразрешима и эквивалентна следующей групповой проблеме: является ли полугруппа, порожденная конечным набором пар слов (над групповым алфавитом) группой.^[11]

использованная литература

^ Э. Л. Пост (1946). «Вариант рекурсивно неразрешимой проблемы» (PDF). Бык. Амер. Математика. Soc. 52: 264–269. Дои:10.1090 / с0002-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.
^ Эренфойхт, А.; Кархумяки, Я.; Розенберг, Г. (Ноябрь 1982 г.). «(Обобщенная) проблема почтовой корреспонденции со списками, состоящими из двух слов, разрешима». Теоретическая информатика. 21 (2): 119–144. Дои:10.1016/0304-3975(89)90080-7.
^ Т. Нери (2015). «Неразрешимость в двоичных системах тегов и проблема пост-соответствия для пяти пар слов». В Эрнст В. Майр и Николас Оллингер (ред.). 32-й Международный симпозиум по теоретическим аспектам информатики (STACS 2015). STACS 2015. 30. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. С. 649–661. Дои:10.4230 / LIPIcs.STACS.2015.649.
^ К. Руохонен (1983). «О некоторых вариантах переписки Поста». Acta Informatica. Springer. 19 (4): 357–367. Дои:10.1007 / BF00290732.
^ Майкл Р. Гарей; Дэвид С. Джонсон (1979). Компьютеры и непреодолимость: руководство по теории NP-полноты. W.H. Фримен. п.228. ISBN 0-7167-1045-5.
^ Ю. Гуревич (1991). «Средняя полнота дела» (PDF). J. Comp. Sys. Наука. Elsevier Science. 42 (3): 346–398. Дои:10.1016 / 0022-0000 (91) 90007-Р.
^ В. Халава; М. Хирвенсало; Р. де Вольф (2001). «Отмеченный PCP разрешимый». Теор. Comput. Наука. Elsevier Science. 255: 193–204. Дои:10.1016 / S0304-3975 (99) 00163-2.
^ П. Шамбар; Ph. Schnoebelen (2007). «Проблема пост-внедрения не является примитивно рекурсивной, с приложениями к системам каналов» (PDF). Конспект лекций по информатике. Конспект лекций по информатике. Springer. 4855: 265–276. Дои:10.1007/978-3-540-77050-3_22. ISBN 978-3-540-77049-7.
^ Пол С. Белл; Игорь Потапов (2010). "О неразрешимости проблемы соответствия тождества и ее приложений для словесных и матричных полугрупп". Международный журнал основ информатики. World Scientific. 21.6: 963–978. arXiv:0902.1975. Дои:10.1142 / S0129054110007660.

внешние ссылки

Эйтан М. Гурари. Введение в теорию вычислений, Глава 4, Проблема с перепиской сообщения. Доказательство неразрешимости PCP на основе Грамматики типа 0 по Хомскому.
Донг, Цзин. «Анализ и решение экземпляра PCP». 2012 Национальная конференция по информационным технологиям и компьютерным наукам. В документе описывается эвристическое правило для решения некоторых конкретных случаев PCP.
Онлайн-решатель PCP на основе PHP
PCP НА ДОМУ
PCP - приятная проблема
Решатель PCP на Java

[Post46-1] Э. Л. Пост (1946). «Вариант рекурсивно неразрешимой проблемы» (PDF). Бык. Амер. Математика. Soc. 52: 264–269. Дои:10.1090 / с0002-9904-1946-08555-9.

[sipser05-2] Майкл Сипсер (2005). «Простая неразрешимая проблема». Введение в теорию вычислений (2-е изд.). Thomson Course Technology. С. 199–205. ISBN 0-534-95097-3.

[3] Саломаа, Арто (1981). Драгоценности теории формального языка. Pitman Publishing. С. 74–75. ISBN 0-273-08522-0. Zbl 0487.68064.

[EKR82-4] Эренфойхт, А.; Кархумяки, Я.; Розенберг, Г. (Ноябрь 1982 г.). «(Обобщенная) проблема почтовой корреспонденции со списками, состоящими из двух слов, разрешима». Теоретическая информатика. 21 (2): 119–144. Дои:10.1016/0304-3975(89)90080-7.

[N15-5] Т. Нери (2015). «Неразрешимость в двоичных системах тегов и проблема пост-соответствия для пяти пар слов». В Эрнст В. Майр и Николас Оллингер (ред.). 32-й Международный симпозиум по теоретическим аспектам информатики (STACS 2015). STACS 2015. 30. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. С. 649–661. Дои:10.4230 / LIPIcs.STACS.2015.649.

[Ruohonen83-6] К. Руохонен (1983). «О некоторых вариантах переписки Поста». Acta Informatica. Springer. 19 (4): 357–367. Дои:10.1007 / BF00290732.

[GJ79-7] Майкл Р. Гарей; Дэвид С. Джонсон (1979). Компьютеры и непреодолимость: руководство по теории NP-полноты. W.H. Фримен. п.228. ISBN 0-7167-1045-5.

[Gurevich91-8] Ю. Гуревич (1991). «Средняя полнота дела» (PDF). J. Comp. Sys. Наука. Elsevier Science. 42 (3): 346–398. Дои:10.1016 / 0022-0000 (91) 90007-Р.

[HHW01-9] В. Халава; М. Хирвенсало; Р. де Вольф (2001). «Отмеченный PCP разрешимый». Теор. Comput. Наука. Elsevier Science. 255: 193–204. Дои:10.1016 / S0304-3975 (99) 00163-2.

[CS07-10] П. Шамбар; Ph. Schnoebelen (2007). «Проблема пост-внедрения не является примитивно рекурсивной, с приложениями к системам каналов» (PDF). Конспект лекций по информатике. Конспект лекций по информатике. Springer. 4855: 265–276. Дои:10.1007/978-3-540-77050-3_22. ISBN 978-3-540-77049-7.

[BP10-11] Пол С. Белл; Игорь Потапов (2010). "О неразрешимости проблемы соответствия тождества и ее приложений для словесных и матричных полугрупп". Международный журнал основ информатики. World Scientific. 21.6: 963–978. arXiv:0902.1975. Дои:10.1142 / S0129054110007660.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]