Как это часто бывает с NP-сокращениями, имеет смысл искать подобные проблемы. В частности, трудно кодировать глобальные условия, такие как "видевшие некоторые узлы", в PCP (с полиномиальным количеством плиток), что противопоказывает проблемы с графами, проблемы с упаковкой потребовали бы, чтобы мы кодировали унарные числа в PCP (создавая экспоненциально большой экземпляр), и скоро. Поэтому можно ожидать, что строковая проблема только с локальными ограничениями будет работать лучше всего.
Рассмотрим вариант решения самой короткой общей проблемы суперпоследовательности :
Учитывая две строки с и и , решите, есть ли строка с такой, что и являются подпоследовательностями .| а | = n | б | = m k ∈ N c ∈ Σ + | с | ≤ k a b ca , b ∈ Σ+| а | =n| б | =мk ∈ Nc ∈ Σ+| с | ≤kaбс
Идея состоит в том, чтобы позволить PCP строить суперпоследовательности и слева направо, кодируя в перекрытиях плиток, в которых мы находимся в и соответственно. Он будет использовать одну плитку на символ в , так что соответствует границе BPCP: если мы можем решить этот PCP с помощью плиток, вы можете считать общую суперпоследовательность равной длины, и наоборот.b a b c k ≤ kaбaбсК≤ k
Построение плитки немного утомительно, но довольно понятно. Обратите внимание, что мы не будем создавать плитки, которые не пересылают или b ; такие никогда не могут быть частью кратчайшей общей суперпоследовательности, поэтому они излишни. Их можно легко добавить, не нарушая свойства восстановления.aб
ΣжурналМакс ( м , н )
- Начальные плитки: может начинаться с , или обоих, если они равны.1 б 1сa1б1
- Промежуточные тайлы: может перейти к следующему символу в , в или в обоих, если они равны.в бсaб
- Завершающие плитки: заканчивается последним символом (если последний из уже был просмотрен), аналогичным для или последним символом обоих.в б бсaбб
Это схемы плитки. Обратите внимание, что промежуточные тайлы должны быть созданы для всех пар . Как упомянуто выше, создавайте плитки без только если соответствующие символы в и совпадают.∗(i,j)∈[n]×[m]∗бaб
[ источник ]
Символ означает «все равно»; в реальных тайлах другой символ должен быть скопирован туда. Обратите внимание, что число плиток находится в и каждая плитка имеет длину , поэтому построенный экземпляр BPCP (по алфавиту плюс символы разделения) имеет полиномиальный размер. Кроме того, построение каждой плитки очевидно возможно за полиномиальное время. Таким образом, предлагаемое сокращение действительно является действительным полиномиальным преобразованием, которое сводит NP-полную задачу кратчайшей общей суперпоследовательности к BPCP.Θ ( m n ) 4 log max ( m , n ) + 1 Σ ∪ { 0 , 1 }*Θ ( м н )4 журналаМакс ( м , н ) + 1Σ ∪ { 0 , 1 }
Я думаю, что вы можете доказать, что BPCP является NP-полной, используя сокращение, подобное тому, которое использовалось для доказательства его неразрешимости. Мы прямо докажем, что BPCP является NP-полной, показывая, как свести к ней любую проблему в NP за полиномиальное время.
Стандартное сокращение, используемое для доказательства того, что PCP неразрешимо ( обрисовано здесь в общих чертах ), работает путем построения ряда плиток таким образом, чтобы существовало решение PCP, если есть принимающее вычисление данного TM для строки . Количество плиток, созданных в этом сокращении, многочленно - в частности, количество построенных домино является некоторой функцией от размера алфавита ленты и количества состояний в ТМ. Только домино, размер которого может быть большим является начальным домино, который имеетш шM вес вес написано на нем. Если мы обобщим это сокращение от работы над детерминированными ТМ до работы с недетерминированными ТМ, то это вводит не более некоторого постоянного числа домино, поскольку число переходов конечно. Следовательно, мы можем построить стандартный набор домино для нормального снижения неразрешимости за полиномиальное время.
Учитывая это, мы можем свести любую проблему NP к BPCP следующим образом - учитывая любую проблему NP, она имеет некоторый NTM полиномиальное время, которое выполняется за время . Затем мы можем свести эту проблему к BPCP за полиномиальное время следующим образом - построить стандартный набор домино из , а затем спросить, существует ли решение, использующее домино, где - некоторая полиномиальная функция, которая выражает количество домино, необходимое для существования решения (это, вероятно, что-то вроде , и, конечно, не экспоненциальный). Затем, используя то же доказательство, которое вы используете, чтобы показать, что PCP неразрешимо, вы можете доказать, что существует решение для этого экземпляра BPCP, которое использует не болееp ( n ) M f ( p ( n ) ) f n 2 f ( p ( n ) ) M m p ( n )M p ( n ) M е( р ( н ) ) е N2 е( р ( н ) ) тайлы, если исходный NTM принимает течение шагов. Следовательно, мы имеем сокращение полиномиального времени от каждой проблемы в NP до BPCP, поэтому BPCP труден для NP.M м p ( n )
(Мы также должны показать, что BPCP находится в NP, но это легко; просто недетерминированно угадать, какие доминошки привести в порядок, а затем детерминистически проверьте это).
Надеюсь это поможет!
источник