Dureza NP de revestimentos com peças retangulares (Google Hash Code 2015 Test Round)

11

A Rodada de Teste do Google Hash Code 2015 ( declaração do problema ) perguntou sobre o seguinte problema:

  • entrada: uma grade com alguns quadrados marcados, um limiar T N , uma área máxima A NMTNAN
  • produção: a maior área possível total de um conjunto de rectângulos disjuntos com coordenadas de número inteiro em de modo que cada rectângulo inclui, pelo menos, t quadrados marcados e cada rectângulo tem área de, no máximo, um .MTA

Na terminologia do Google, a grade é uma pizza, os quadrados marcados são presunto e os retângulos separados são fatias.

Podemos reformular claramente esse problema para um problema de decisão adicionando uma entrada adicional e deixe a resposta ser "existe um conjunto de retângulos disjuntos que satisfazem as condições cuja área total é de pelo menos n quadrados".nNn

Minha pergunta: embora o problema do Google tenha solicitado aos candidatos que encontrassem uma solução "o melhor possível" para o problema de computação em uma instância específica, acho que é provável que o problema geral (em sua formulação de decisão) seja NP-completo. No entanto, não consigo encontrar uma redução para mostrar a dureza NP. (A associação ao NP é imediata.) Como provar que esse problema é difícil ao NP?

44{0,1,2,3}×{0,1,2,3}(1,1)(0,2)(2,2)X

..X.
.X..
..X.
....

A=66T=1

aaAa
bBcc
bbCc
bbcc

A=3T=2

XXX
.X.
...

Não se pode fazer melhor do que cobrir apenas três quadrados:

AAA
.X.
...

ou

XBX
.B.
.b.

(lembre-se de que os retângulos na partição não podem se sobrepor).

Com outras pessoas analisando essa questão, tentamos reduções no empacotamento de caixas, cobrindo problemas, ciclos 3-SAT e Hamiltoniano, e não conseguimos fazer com que uma funcionasse.

a3nm
fonte

Respostas:

10

Este é um esboço de uma redução do MONOTONE CUBIC PLANAR 1-3 SAT:


φ=C1C2...CmCjCj=(j,1j,2j,3)
φCj contém exatamente um literal verdadeiro.

O problema permanece NP-completo, mesmo que todos os literais nas cláusulas sejam positivos (MONOTONE), se o gráfico construído conectando cláusulas com variáveis ​​for planar (PLANAR) e cada variável estiver contida em exatamente 3 cláusulas (CUBIC) (C. Moore e JM Robson, Problemas difíceis com ladrilhos simples, Discrete Comput. Geom.26 (2001), 573-590.

T=3,A=6

A+

insira a descrição da imagem aqui

xixi=TRUExi=FALSE

insira a descrição da imagem aqui

CjLi,1,Li,2,Li,3

insira a descrição da imagem aqui

Por fim, podemos criar turnos e ativar dispositivos para transmitir os sinais de acordo com o gráfico planar subjacente e ajustar os pontos finais:

insira a descrição da imagem aqui

HA

H/3AH/3

H/3AH/3

Vor
fonte