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

11

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 NM.T.N.ZAN.
  • 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 AM.T.ZA

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”.nN.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:44{0,1,2),3)}×{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:ZA=66T.=1

aaAa
bBcc
bbCc
bbcc

Na poniższej siatce, przy i T = 2 :ZA=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.

a3nm
źródło

Odpowiedzi:

10

Oto szkic redukcji z MONOTONE CUBIC PLANAR 1-3 SAT:


φ=do1do2)...domdojotdojot=(jot,1jot,2)jot,3))
φdojot 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),ZA=6

ZA+-

wprowadź opis zdjęcia tutaj

xjaxja=T.RUmixja=faZAL.S.mi

wprowadź opis zdjęcia tutaj

dojotL.ja,1,L.ja,2),L.ja,3)

wprowadź opis zdjęcia tutaj

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:

wprowadź opis zdjęcia tutaj

H.ZA

H./3)ZAH./3)

H./3)ZAH./3)

Vor
źródło