Проблема с перепиской

Не путать с другой проблемой Поста о существовании несравнимых степеней Тьюринга.

Не путать с теоремой PCP .

Проблема переписки Поста — это неразрешимая проблема решения , которая была предложена Эмилем Постом в 1946 году. Поскольку она проще, чем проблема остановки и проблема Entscheidungs, ее часто используют в доказательствах неразрешимости.

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

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

$\alpha _{i_{1}}\ldots \alpha _{i_{K}}=\beta _{i_{1}}\ldots \beta _{i_{K}}.$

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

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

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

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

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

$g(w)=h(w)$.

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

${\begin{bmatrix}a\\ab\end{bmatrix}}$

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

${{\begin{bmatrix}bc\\ca\end{bmatrix}},{\begin{bmatrix}a\\ab\end{bmatrix}},{\begin{bmatrix}ca\\a\end{bmatrix}},{\begin{bmatrix}abc\\c\end{bmatrix}}}$.

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

${{\begin{bmatrix}a\\ab\end{bmatrix}},{\begin{bmatrix}bc\\ca\end{bmatrix}},{\begin{bmatrix}a\\ab\end{bmatrix}},{\begin{bmatrix}abc\\c\end{bmatrix}}}$.

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

${{\begin{bmatrix}abc\\ab\end{bmatrix}},{\begin{bmatrix}ca\\a\end{bmatrix}},{\begin{bmatrix}acc\\ba\end{bmatrix}}}$.

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

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

Пример 1

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

1 ​	2 ​	3 ​
а	аб	бба

б 1	б 2	б 3
да	аа	бб

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

$\alpha _{3}\alpha _{2}\alpha _{3}\alpha _{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) и т. д.; то есть, когда решение существует, существует бесконечно много решений такого повторяющегося типа.

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

Удобный способ просмотреть экземпляр задачи о переписке Поста — это набор блоков вида

α я

β я

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

а

да

я = 1

аб

аа

я = 2

бба

бб

я = 3

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

бба

бб

я ₁ = 3

аб

аа

я ₂ = 2

бба

бб

я ₃ = 3

а

да

я ₄ = 1

Пример 2

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

бб

б

1

аб

нет

2

с

до нашей эры

3

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

бб

б

1

аб

нет

2

аб

нет

2

аб

нет

2

с

до нашей эры

3

неразрешимости

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

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

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

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

101101110 q ₇ 00110.

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

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

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

д 0 х #

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

а

а

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

д 4 0

1 кв. 7

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

qf а

q ж

ф ак

q ж

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

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

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

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

д 0 101#

qq01 1

1 q 4

0

0

1

1

#

#

1

1

q 4 0

1 q1q2

1

1

#

#

1

1

1 кв 2 1

д 8 10

#

#

1 q1q8

qq8

1

1

0

0

#

#

д 8 1

qq8

0

0

#

#

д 8 0

qq8

#

#

qq8

#

#

...

Варианты

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

• Проблему можно сформулировать в терминах моноидных морфизмов f , g из свободного моноида B ^∗ к свободному моноиду A ^∗ где B имеет размер n . Задача состоит в том, чтобы определить, есть ли слово w в B. ⁺ такой, что ж ( ш ) = г ( ш ).
• Условие того, что алфавит $A$ иметь не менее двух символов, поскольку задача разрешима, если $A$ имеет только один символ.
• Простой вариант — зафиксировать n — количество плиток. Эта задача разрешима, если n ≤ 2, но остается неразрешимой при n ≥ 5. Неизвестно, разрешима ли задача при 3 ≤ n ≤ 4.
• Циркулярная спрашивает , проблема переписки Почты являются ли индексы $i_{1},i_{2},\ldots$ можно найти такое, что $\alpha _{i_{1}}\cdots \alpha _{i_{k}}$ и $\beta _{i_{1}}\cdots \beta _{i_{k}}$ являются сопряженными словами , т. е. равны по модулю вращения. Этот вариант неразрешим.
• Одним из наиболее важных вариантов PCP является ограниченная задача соответствия Поста , которая спрашивает, можем ли мы найти совпадение, используя не более k плиток, включая повторяющиеся плитки. Перебор методом грубой силы решает задачу за время O(2 ^к ), но это может быть сложно улучшить, поскольку проблема NP-полна . В отличие от некоторых NP-полных задач, таких как проблема логической выполнимости , также было показано, что небольшая вариация ограниченной задачи является полной для RNP, а это означает, что она остается сложной, даже если входные данные выбираются случайным образом (это сложно в среднем по равномерному распределению). распределенные входы).
• Другой вариант PCP называется отмеченной задачей почтовой переписки , в которой каждый $\alpha _{i}$ должно начинаться с другого символа, и каждый $\beta _{i}$ также должно начинаться с другого символа. Халава, Хирвенсало и де Вольф показали, что эта вариация разрешима за экспоненциальное время . Более того, они показали, что если это требование немного ослабить, так что только один из первых двух символов должен отличаться (так называемая проблема почтовой переписки с 2-мя пометками), проблема снова становится неразрешимой.
• Проблема пост-встраивания — это еще один вариант поиска индексов. $i_{1},i_{2},\ldots$ такой, что $\alpha _{i_{1}}\cdots \alpha _{i_{k}}$ является (разбросанным) подсловом слова $\beta _{i_{1}}\cdots \beta _{i_{k}}$. Этот вариант легко разрешим, поскольку при наличии некоторых решений существует, в частности, решение длины один. Более интересной является регулярных проблема встраивания сообщений , дальнейший вариант, в котором ищутся решения, принадлежащие данному регулярному языку (представленные, например, в форме регулярного выражения на множестве $\{1,\ldots ,N\}$). Проблема регулярного пост-встраивания все еще разрешима, но из-за добавленного регулярного ограничения она имеет очень высокую сложность, которая доминирует над каждой многорекурсивной функцией.
• Проблема соответствия идентичности (ICP) спрашивает, может ли конечный набор пар слов (в групповом алфавите) генерировать пару тождеств с помощью последовательности конкатенаций. Проблема неразрешима и эквивалентна следующей групповой проблеме: является ли полугруппа, порожденная конечным набором пар слов (над групповым алфавитом), группой.

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

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