NP-hardness dari penutup dengan potongan persegi panjang (Google Hash Code 2015 Test Round)

Putaran Tes Google Hash Code 2015 ( pernyataan masalah ) bertanya tentang masalah berikut:

• input: kisi dengan beberapa kotak yang ditandai, ambang , area maksimal$M$$T \in \mathbb{N}$$A \in \mathbb{N}$
• Output: total luas kemungkinan terbesar dari serangkaian persegi panjang menguraikan dengan koordinat bilangan bulat di sehingga setiap persegi panjang mencakup setidaknya kotak ditandai dan setiap persegi panjang memiliki wilayah paling .$M$$T$$A$

Dalam terminologi Google, grid adalah pizza, kotak yang ditandai adalah ham, dan persegi panjang yang terpisah adalah irisan.

Kami dapat dengan jelas menguraikan masalah ini menjadi masalah keputusan dengan menambahkan input tambahan dan membiarkan jawabannya menjadi "apakah ada seperangkat persegi panjang terputus-putus yang memenuhi kondisi yang luas totalnya setidaknya kotak".$n \in \mathbb{N}$$n$

Pertanyaan saya: sementara masalah Google meminta para kandidat untuk menemukan solusi yang "sebaik mungkin" untuk masalah perhitungan pada contoh spesifik, saya pikir ada kemungkinan bahwa masalah umum (dalam frasa keputusannya) adalah NP-complete. Namun, saya tidak dapat menemukan pengurangan untuk menunjukkan kekerasan NP. (Keanggotaan NP segera.) Bagaimana membuktikan bahwa masalah ini sulit NP?

Beberapa contoh mengikuti, untuk membantu memvisualisasikan masalah. Pertimbangkan dengan$4$ kotak { 0 , 1 , 2 , 3 } × { 0 , 1 , 2 , 3 } , dengan kotak yang ditandai ( 1 , 1 ) , ( 0 , 2 ) dan ( 2 , 2 ) , diwakili grafis dengan$4$$\{0, 1, 2, 3\} \times \{0, 1, 2, 3\}$$(1, 1)$$(0, 2)$$(2, 2)$X untuk mengindikasikan kotak yang ditandai:

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

Set (persegi panjang paling banyak 6 kotak) dan T = 1 (setidaknya satu persegi ditandai per persegi panjang), solusi optimal (yang mencakup seluruh grid) adalah dengan mengambil persegi panjang berikut:$A = 6$$6$$T = 1$

aaAa
bBcc
bbCc
bbcc

Pada kisi berikut, dengan dan T = 2 :$A = 3$$T = 2$

XXX
.X.
...

Seseorang tidak dapat melakukan lebih baik daripada hanya mencakup tiga kotak:

AAA
.X.
...

atau

XBX
.B.
.b.

(ingat bahwa persegi panjang di partisi tidak dapat tumpang tindih).

Dengan orang lain melihat pertanyaan ini, kami mencoba reduksi dari pengemasan bin, mencakup masalah, siklus 3-SAT, dan Hamiltonian, dan kami tidak berhasil membuatnya bekerja.

Ini adalah sketsa pengurangan dari MONOTONE CUBIC PLANAR 1-3 SAT:

Definisi [Masalah SAT 1-3]:
Input: Rumus 3-CNF , di mana setiap klausul C j berisi tepat tiga literal: C j = ( ℓ j , 1 ∨ ℓ j , 2 ∨ ℓ j , 3 ) . Pertanyaan: Apakah ada tugas yang memuaskan untuk φ sehingga setiap klausa C $\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$ mengandung tepat satu literal sejati.

Masalahnya tetap NP-lengkap bahkan jika semua literal dalam klausa adalah positif (MONOTONE), jika grafik dibangun menghubungkan klausa dengan variabel adalah planar (PLANAR) dan setiap variabel terkandung dalam tepat 3 klausa (CUBIC) (C. Moore dan JM Robson, Masalah ubin keras dengan ubin sederhana, Komputasi Diskrit. 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}$

Terakhir, kita dapat membuat shift dan menghidupkan gadget untuk membawa sinyal sesuai dengan grafik planar yang mendasarinya dan menyesuaikan titik akhir:

$H$$A$ .

$H /3$$A H / 3$ ) dan tidak ada ham yang tetap terbuka.

$H /3$$A H / 3$