Полиномиальная редукция из любой NP-полной задачи в ограниченную PCP

18

Учебники повсюду предполагают, что проблема ограниченной почтовой корреспонденции является NP-полной (не более индексов допускается с повторениями). Тем не менее, нигде не показано простого (как, например, то, что может понять студент) полиномиального сокращения времени из другой NP-полной задачи.N

Однако каждое сокращение, которое я могу придумать, является экспоненциальным (по или по размеру ряда) во время выполнения. Возможно, можно показать, что оно сводимо к SAT?N

Джон
источник

Ответы:

10

Как это часто бывает с NP-сокращениями, имеет смысл искать подобные проблемы. В частности, трудно кодировать глобальные условия, такие как "видевшие некоторые узлы", в PCP (с полиномиальным количеством плиток), что противопоказывает проблемы с графами, проблемы с упаковкой потребовали бы, чтобы мы кодировали унарные числа в PCP (создавая экспоненциально большой экземпляр), и скоро. Поэтому можно ожидать, что строковая проблема только с локальными ограничениями будет работать лучше всего.

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

Учитывая две строки с и и , решите, есть ли строка с такой, что и являются подпоследовательностями .| а | = n | б | = m k N c Σ + | с | k a b ca,bΣ+|a|=n|b|=mkNcΣ+|c|kabc

Идея состоит в том, чтобы позволить PCP строить суперпоследовательности и слева направо, кодируя в перекрытиях плиток, в которых мы находимся в и соответственно. Он будет использовать одну плитку на символ в , так что соответствует границе BPCP: если мы можем решить этот PCP с помощью плиток, вы можете считать общую суперпоследовательность равной длины, и наоборот.b a b c k kababckk

Построение плитки немного утомительно, но довольно понятно. Обратите внимание, что мы не будем создавать плитки, которые не пересылают или b ; такие никогда не могут быть частью кратчайшей общей суперпоследовательности, поэтому они излишни. Их можно легко добавить, не нарушая свойства восстановления.ab

Σlogmax(m,n)

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

Это схемы плитки. Обратите внимание, что промежуточные тайлы должны быть созданы для всех пар . Как упомянуто выше, создавайте плитки без только если соответствующие символы в и совпадают.(я,J)[N]×[м]*бaб

введите описание изображения здесь
[ источник ]

Символ означает «все равно»; в реальных тайлах другой символ должен быть скопирован туда. Обратите внимание, что число плиток находится в и каждая плитка имеет длину , поэтому построенный экземпляр BPCP (по алфавиту плюс символы разделения) имеет полиномиальный размер. Кроме того, построение каждой плитки очевидно возможно за полиномиальное время. Таким образом, предлагаемое сокращение действительно является действительным полиномиальным преобразованием, которое сводит NP-полную задачу кратчайшей общей суперпоследовательности к BPCP.Θ ( m n ) 4 log max ( m , n ) + 1 Σ { 0 , 1 }*Θ(мN)4журналМаксимум(м,N)+1Σ{0,1}

Рафаэль
источник
Хороший ответ. Я предполагаю самое простое известное сокращение.
Мохаммад Аль-Туркистани
8

Я думаю, что вы можете доказать, что 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п(N)Mе(п(N))еN2е(п(N))тайлы, если исходный NTM принимает течение шагов. Следовательно, мы имеем сокращение полиномиального времени от каждой проблемы в NP до BPCP, поэтому BPCP труден для NP.Mмп(N)

(Мы также должны показать, что BPCP находится в NP, но это легко; просто недетерминированно угадать, какие доминошки привести в порядок, а затем детерминистически проверьте это).

Надеюсь это поможет!

templatetypedef
источник
Это помогает в некотором роде, хотя я все еще предпочел бы сокращение непосредственно от другой проблемы.
Джон
@ john- Есть ли какая-то особая причина, по которой вы хотите свести известную NP-полную проблему к BPCP? Приведенное выше доказательство показывает, что проблема является NP-полной и подчеркивает связь между неразрешимостью PCP и NP-полнотой BPCP.
templatetypedef
Чисто образовательная причина, так как обычно большинство учебников используют метод прямого сокращения, чтобы доказать NP-полноту и понять, что эта проблема ничем не отличается от остальных в этом отношении.
Джон
1
@john: Конечно, вы можете использовать сокращение templatetypedef для любой NP-полной задачи (которая является прямой), но это не заставит ее использовать структуру выбранной проблемы. В образовательных целях это блестяще, потому что обычно вы видите только одно неуменьшающее доказательство того, что проблема является NP-полной.
Рафаэль