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 obszarT ∈ N A ∈ $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 .T $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 n 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 4 { 0 , 1 , 2 , 3 } × { 0 , 1 , 2 , 3 } , z zaznaczonymi kwadratami ( 1 , 1 ) , ( 0 , 2 ) i ( 2 , 2 ) , 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 6 kwadratów) i T = 1 (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 T = 2 :$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.

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$

$H /3$$A H / 3$