Проблема соответствия Поста

Проблема соответствия Поста (также известная как проблема соответствия Поста, PCP) — это алгоритмически неразрешимая задача, сформулированная американским математиком Эмилем Постом в 1946 году. Она относится к классу проблем, для которых не существует общего алгоритма, способного дать ответ «да» или «нет» для всех возможных входных данных. PCP является одной из классических неразрешимых задач теории алгоритмов и играет ключевую роль в доказательстве неразрешимости других проблем, особенно в области формальных языков и грамматик.

Формулировка задачи

Задача формулируется следующим образом. Даны два списка строк (слов) над некоторым алфавитом: A = (a₁, a₂, ..., aₙ) и B = (b₁, b₂, ..., bₙ). Требуется определить, существует ли непустая последовательность индексов i₁, i₂, ..., iₖ (где 1 ≤ iⱼ ≤ n), такая, что конкатенация строк из списка A в этой последовательности совпадает с конкатенацией строк из списка B в той же последовательности:

aᵢ₁ aᵢ₂ ... aᵢₖ = bᵢ₁ bᵢ₂ ... bᵢₖ

Последовательность индексов называется решением задачи. Если такое решение существует, говорят, что экземпляр PCP имеет решение. Если нет — экземпляр не имеет решения.

Пример

Рассмотрим простой пример. Пусть алфавит {0, 1}. Список A = (1, 10111, 10), список B = (111, 10, 0). Можно ли найти последовательность индексов? Попробуем последовательность (2, 1, 1, 3):

• A: a₂ a₁ a₁ a₃ = 10111 1 1 10 = 101111110
• B: b₂ b₁ b₁ b₃ = 10 111 111 0 = 101111110

Результаты совпадают. Значит, последовательность (2, 1, 1, 3) является решением данного экземпляра PCP.

Неразрешимость

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

Модифицированная проблема соответствия Поста

Существует модифицированная версия задачи, называемая модифицированной проблемой соответствия Поста (MPCP). В MPCP начальная пара индексов фиксирована: первая пара должна быть (1, 1). То есть, требуется найти последовательность (1, i₂, ..., iₖ), такую что a₁ aᵢ₂ ... aᵢₖ = b₁ bᵢ₂ ... bᵢₖ. MPCP также неразрешима, и её часто используют для доказательства неразрешимости других задач, так как сведение к ней может быть проще.

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

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

Примеры проблем, неразрешимость которых доказывается через PCP

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

Варианты и обобщения

Существует несколько вариантов PCP, которые могут быть как разрешимыми, так и неразрешимыми в зависимости от ограничений.

• PCP с ограничением на длину решения: Если заранее известна максимальная длина последовательности индексов, задача становится разрешимой (можно перебрать все возможные последовательности).
• PCP над однобуквенным алфавитом: Если алфавит состоит из одного символа, задача становится разрешимой. В этом случае строки представляют собой целые числа (длины строк), и задача сводится к решению системы линейных диофантовых уравнений.
• PCP с ограничением на количество пар: Если количество пар n равно 1, задача тривиальна: решение существует, если a₁ = b₁. Если n = 2, задача также разрешима. Для n = 7 задача остаётся неразрешимой. Точная граница, при которой задача становится неразрешимой, была предметом исследований, но известно, что для n = 2 она разрешима, а для n = 7 — нет.
• Вероятностная PCP: В теории сложности вычислений существует понятие вероятностной проверяемой системы доказательств (PCP — Probabilistically Checkable Proof), которое является фундаментальным для доказательства теорем о неаппроксимируемости. Несмотря на одинаковую аббревиатуру, это совершенно другая концепция, не связанная напрямую с проблемой соответствия Поста.

Значение для теории алгоритмов

Проблема соответствия Поста занимает важное место в теории алгоритмов как классический пример неразрешимой задачи, которая, в отличие от проблемы остановки, формулируется в чисто комбинаторных терминах, без обращения к понятию машины Тьюринга. Это делает её удобным инструментом для доказательства неразрешимости в различных областях, где понятие «вычисления» не является центральным. PCP демонстрирует, что даже простые на первый взгляд комбинаторные задачи могут быть алгоритмически неразрешимыми.

Источники

• Post, E. L. (1946). A variant of a recursively unsolvable problem. Bulletin of the American Mathematical Society, 52(4), 264-268.
• Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley.
• Sipser, M. (2012). Introduction to the Theory of Computation (3rd ed.). Cengage Learning.
• Ахо, А., Ульман, Дж. (1978). Теория синтаксического анализа, перевода и компиляции. Том 1. Мир.