Uma redução polinomial de qualquer problema NP-completo para PCP limitado

Em todo lugar, os livros de texto assumem que o Problema de correspondência pós encadernada é NP completo (não são permitidos mais do que índices permitidos com repetições). No entanto, em nenhum lugar é mostrada uma redução de tempo polinomial simples (como em algo que um aluno de graduação pode entender) de outro problema NP-completo.$N$

No entanto, toda redução que consigo pensar é exponencial (por ou pelo tamanho da série) em tempo de execução. Talvez possa ser demonstrado que é redutível ao SAT?$N$

Como geralmente ocorre com reduções de NP, faz sentido procurar problemas semelhantes . Em particular, é difícil codificar condições globais que "viram alguns nós" no PCP (com muitos blocos polinomialmente), o que contra-indica problemas gráficos, problemas de empacotamento exigiriam a codificação de números unários no PCP (criando uma instância exponencialmente grande) e em breve. Portanto, um problema de cadeia de caracteres com apenas restrições locais pode funcionar melhor.

Considere a versão de decisão do menor problema comum de superseqüência :

Dadas duas cadeias $a,b \in \Sigma^+$ com $|a|=n$ e $|b|=m$ e , decidir se há uma cadeia de com tal que a e b são subsequências de c . c ∈ Σ + | c | ≤ $k \in \mathbb{N}$$c \in \Sigma^+$$|c| \leq k$$a$$b$$c$

A idéia é deixar superseqüências PCP construção de e b , da esquerda para a direita, codificando em sobreposições das telhas em que posição estamos em um e b , respectivamente. Ele usará um bloco por símbolo em c , de modo que k corresponde ao limite do BPCP: se pudermos resolver esse PCP com blocos ≤ k , você poderá ler a superseqüência comum de comprimento igual e vice-versa.$a$$b$$a$$b$$c$$k$$\leq k$

A construção dos azulejos é um pouco entediante, mas bastante clara. Observe que não criaremos blocos que não encaminham ou b ; isso nunca pode fazer parte de uma menor superseqüência comum, portanto é supérfluo. Eles podem ser facilmente adicionados sem quebrar as propriedades da redução.$a$$b$

$\Sigma$$\log \max(m,n)$

• Ladrilhos iniciais : pode começar com , ou ambos, se forem iguais.um 1 b $c$$a_1$$b_1$
• Ladrilhos intermediários: pode prosseguir com o próximo símbolo em , em ou em ambos, se forem iguais.a $c$$a$$b$
• Ladrilhos de terminação: termina com o último símbolo de (se o último de já foi visto), semelhante para , ou com o último símbolo de ambos.a b $c$$a$$b$$b$

Estes são os esquemas de blocos. Observe que os blocos intermediários devem ser instanciados para todos os pares . Como mencionado acima, criar as telhas sem somente se os respectivos personagens em e jogo.∗ a $(i,j) \in [n]\times [m]$$*$$a$$b$

^{[ fonte ]}

O é simbólico para "não me importo"; nos blocos reais, o outro símbolo terá que ser copiado lá. Observe que o número de blocos está em e cada bloco possui comprimento ; portanto, a instância BPCP construída (sobre o alfabeto mais símbolos de separação) tem tamanho polinomial. Além disso, a construção de cada ladrilho é claramente possível em tempo polinomial. Portanto, a redução proposta é de fato uma transformação polinomial válida que reduz o menor problema comum de superseqüência comum de NP-completo para BPCP.Θ ( m n ) 4 log max ( m , n ) + 1 Σ ∪ { 0 , 1 $*$$\Theta(mn)$$4\log \max(m,n) + 1$$\Sigma \cup \{0,1\}$

Eu acho que você pode provar que o BPCP é NP-completo usando uma redução semelhante à usada para provar sua indecidibilidade. Provaremos diretamente que o BPCP é NP-completo, mostrando como reduzir qualquer problema no NP a ele em tempo polinomial.

A redução padrão usada para provar que o PCP é indecidível ( esboçado aqui ) funciona através da construção de uma série de blocos de modo que exista uma solução de PCP se houver um cálculo aceitável de uma determinada TM em uma sequência . O número de peças criadas nessa redução é polinomialmente grande - especificamente, o número de peças de dominó construídas é uma função do tamanho do alfabeto da fita e do número de estados na TM. O único dominó cujo tamanho pode ser grande é o dominó inicial, que temw $M$$w$$w$escrito nele. Se generalizarmos essa redução de trabalhar em TMs determinísticas para trabalhar em TMs não determinísticas, isso introduzirá no máximo um número constante de dominós, já que o número de transições é finito. Consequentemente, podemos construir o conjunto padrão de dominós para a redução normal de indecidibilidade no tempo polinomial.

Diante disso, podemos reduzir qualquer problema de NP para BPCP da seguinte maneira - dado qualquer problema de NP, ele possui NTM tempo polinomial que corre no tempo p ( n ) . Podemos então reduzir esse problema ao BPCP no tempo polinomial da seguinte maneira - construa o conjunto padrão de dominós de M e pergunte se existe uma solução que use f ( p ( n ) ) dominó, onde f é alguma função polinomial que expressa a número de dominós necessários para a solução existir (provavelmente é algo como n 2 e certamente não é exponencial). Em seguida, usando a mesma prova que você usa para mostrar que o PCP é indecidível, você pode provar que há uma solução para essa instância BPCP que usa no máximo f $M$$p(n)$$M$$f(p(n))$$f$$n^2$ ladrilhos se o NTM M originalaceitar m dentro de p ( n ) etapas. Conseqüentemente, temos uma redução no tempo polinomial de todos os problemas no NP para o BPCP, portanto, o BPCP é difícil para o NP.$f(p(n))$$M$$m$$p(n)$

(Devemos também mostrar que o BPCP está no NP, mas isso é fácil; basta adivinhar de forma não-determinística quais dominós colocar em ordem e depois verificar deterministicamente).

Espero que isto ajude!