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

18

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

John
fonte

Respostas:

10

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Σ+ 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 | kkNcΣ+|c|kabc

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.ababckk

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.ab

Σlogmax(m,n)

  • Ladrilhos iniciais : pode começar com , ou ambos, se forem iguais.um 1 b 1ca1b1
  • Ladrilhos intermediários: pode prosseguir com o próximo símbolo em , em ou em ambos, se forem iguais.a bcab
  • 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 bcabb

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 b(i,j)[n]×[m]ab

insira a descrição da imagem aqui
[ 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 }Θ(mn)4logmax(m,n)+1Σ{0,1}

Rafael
fonte
Boa resposta. Eu acho que a redução mais simples conhecida.
Mohammad Al-Turkistany
8

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 wMwwescrito 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 (Mp(n)Mf(p(n))fn2 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))Mmp(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!

templatetypedef
fonte
Isso ajuda de alguma forma, embora eu ainda prefira uma redução diretamente de outro problema.
john
@ john- Existe um motivo específico que você deseja reduzir um problema conhecido de NP-complete ao BPCP? A prova acima mostra que o problema é NP-complete e destaca a conexão entre a indecidibilidade do PCP e a NP-BP.
templatetypedef
Razão puramente educacional, uma vez que normalmente a maioria dos livros de texto usa o método de redução direta para comprovar a completude do NP e entender que esse problema não é diferente do restante nesse aspecto.
john
1
@ john: É claro que você pode usar a redução do templatetypedef em qualquer problema NP-completo (que é direto), mas isso não fará com que ele explore a estrutura do problema escolhido. Para fins educacionais, isso é brilhante, porque geralmente você vê apenas uma prova de não redução de que um problema é NP-completo.
Raphael