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

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 , uma área máxima $M$ $T \in \mathbb{N}$ $A \in \mathbb{N}$
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, quadrados marcados e cada rectângulo tem área de, no máximo, . $M$ $T$ $A$

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 quadrados". $n \in \mathbb{N}$ $n$

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?

$4$ $4$ $\{0, 1, 2, 3\} \times \{0, 1, 2, 3\}$ $(1, 1)$ $(0, 2)$ $(2, 2)$ X

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

$A = 6$ $6$ $T = 1$

aaAa
bBcc
bbCc
bbcc

$A = 3$ $T = 2$

XXX
.X.
...

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

AAA
.X.
...

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.

complexity-theory reductions np-hard a3nm
fonte

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

$\varphi = C_1 \land C_2 \land ... \land C_m$ $C_j$ $C_j = (\ell_{j,1} \lor \ell_{j,2} \lor \ell_{j,3})$
$\varphi$ $C_j$ 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$