Twardość NP pokrycia kawałkami prostokątnymi (Google Hash Code 2015 Round Round)

Kodeks Hash 2015 Okrągły testowania Google ( oświadczenie problemem ) poprosił o następującym problemem:

dane wejściowe: siatka z zaznaczonymi kwadratami, próg , maksymalny obszar $M$ $T \in \mathbb{N}$ $A \in \mathbb{N}$
Wydajność: największa powierzchnia całkowita zestawu rozłącznych prostokątów o współrzędnych całkowitą w tak, że każdy prostokąt zawiera co najmniej oznaczone prostokątem pola, a każdy ma powierzchnię co najwyżej . $M$ $T$ $A$

W terminologii Google siatka to pizza, zaznaczone kwadraty to szynka, a rozłączne prostokąty to plasterki.

Możemy wyraźnie przeformułować ten problem na problem decyzyjny, dodając dodatkowe dane wejściowe i niech odpowiedź brzmi „czy istnieje zestaw rozłącznych prostokątów spełniających warunki, których łączna powierzchnia wynosi co najmniej kwadratów”. $n \in \mathbb{N}$ $n$

Moje pytanie: podczas gdy problem Google wymagał od kandydatów znalezienia rozwiązania, które jest „tak dobre, jak to możliwe” dla problemu obliczeniowego w konkretnym przypadku, myślę, że prawdopodobnie ogólny problem (w jego sformułowaniu decyzji) jest NP-kompletny. Nie mogę jednak znaleźć redukcji pokazującej twardość NP. (Członkostwo w NP jest natychmiastowe.) Jak udowodnić, że ten problem jest trudny w NP?

Poniżej podano kilka przykładów, które pomagają zwizualizować problem. Rozważ siatkę na , z zaznaczonymi kwadratami , i , reprezentowanymi graficznie za pomocą aby zaznaczyć oznaczone kwadraty: $4$ $4$ $\{0, 1, 2, 3\} \times \{0, 1, 2, 3\}$ $(1, 1)$ $(0, 2)$ $(2, 2)$ X

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

Ustaw (prostokąty co najwyżej kwadratów) i (co najmniej jeden zaznaczony kwadrat na prostokąt), optymalnym rozwiązaniem (obejmującym całą siatkę) jest przyjęcie następujących prostokątów: $A = 6$ $6$ $T = 1$

aaAa
bBcc
bbCc
bbcc

Na poniższej siatce, przy i : $A = 3$ $T = 2$

XXX
.X.
...

Nie można zrobić nic lepszego niż pokrycie tylko trzech kwadratów:

AAA
.X.
...

lub

XBX
.B.
.b.

(pamiętaj, że prostokąty w partycji nie mogą się pokrywać).

Gdy inni ludzie patrzyli na to pytanie, próbowaliśmy redukcji z pakowania pojemników, obejmujących problemy, cykle 3-SAT i hamiltonowskie, i nie udało nam się zdobyć jednego do pracy.

complexity-theory reductions np-hard

— a3nm
źródło

Oto szkic redukcji z 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$ zawiera dokładnie jeden prawdziwy literał.

Problem pozostaje NP-zupełny, nawet jeśli wszystkie literały w klauzulach są dodatnie (MONOTONE), jeśli wykresy budujące klauzule łączące ze zmiennymi są płaskie (PLANAR) i każda zmienna jest zawarta w dokładnie 3 klauzulach (CUBIC) (C. Moore i JM Robson, Trudne problemy z układaniem płytek w przypadku prostych płytek, Discrete Comput. Geom. 26 (2001), 573-590.).

$T=3, A=6$

$A$ $+$ $-$

$x_i$ $x_i = TRUE$ $x_i = FALSE$

$C_j$ $L_{i,1}, L_{i,2}, L_{i,3}$

Wreszcie możemy zbudować gadżety z przesunięciem i obracaniem, aby przenosić sygnały zgodnie z leżącym pod nimi wykresem planarnym i dostosowywać punkty końcowe:

$H$ $A$

$H /3$ $A H / 3$

— Vor
źródło