NP-твердость покрытия прямоугольными кусочками (Google Hash Code 2015 Test Round)

Тестовый раунд Google Hash Code 2015 ( формулировка проблемы ) задал вопрос о следующей проблеме:

• вход: сетка с несколькими отмеченными квадратами, порог , максимальная площадьT ∈ N A ∈ $M$$T \in \mathbb{N}$$A \in \mathbb{N}$
• Выход: наибольшая возможная площадь множества непересекающихся прямоугольников с целыми координатами в общей таким образом, что каждый прямоугольник включает , по меньшей мере , отмеченные квадраты и каждый прямоугольник имеет область в большинстве .Т $M$$T$$A$

В терминологии Google сетка - это пицца, отмеченные квадраты - ветчина, а непересекающиеся прямоугольники - это кусочки.

Мы можем четко перефразировать эту проблему в решение проблемы, добавив дополнительный ввод и пусть ответ будет "есть ли набор непересекающихся прямоугольников, удовлетворяющих условиям, общая площадь которых не менее квадратов".$n \in \mathbb{N}$$n$

Мой вопрос: в то время как проблема Google попросила кандидатов найти решение, которое «настолько хорошо, насколько это возможно» для задачи вычислений в конкретном случае, я думаю, что вполне вероятно, что общая проблема (в формулировке ее решения) является NP-полной. Тем не менее, я не могу найти снижение, чтобы показать NP-твердость. (Членство в NP является немедленным.) Как доказать, что эта проблема сложна для NP?

Ниже приведено несколько примеров, чтобы помочь визуализировать проблему. Рассмотрим сетку на , с отмеченными квадратами , и , графически представленный для обозначения отмеченных квадратов:4 { 0 , 1 , 2 , 3 } × { 0 , 1 , 2 , 3 } ( 1 , 1 ) ( 0 , 2 ) ( 2 , 2 $4$$4$$\{0, 1, 2, 3\} \times \{0, 1, 2, 3\}$$(1, 1)$$(0, 2)$$(2, 2)$X

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

Установите (прямоугольники не более квадратов) и (хотя бы один помеченный квадрат на прямоугольник), оптимальное решение (которое охватывает всю сетку) - это взять следующие прямоугольники:6 T = $A = 6$$6$$T = 1$

aaAa
bBcc
bbCc
bbcc

На следующей сетке, с и :T = $A = 3$$T = 2$

XXX
.X.
...

Нельзя сделать лучше, чем покрыть только три квадрата:

AAA
.X.
...

или же

XBX
.B.
.b.

(помните, что прямоугольники в разделе не могут перекрываться).

Когда другие люди смотрели на этот вопрос, мы попытались сократить объем упаковки бина, охватив проблемы, 3-SAT и гамильтоновы циклы, и нам не удалось заставить его работать.

Это эскиз сокращения от 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$ содержит ровно один истинный литерал.

Проблема остается NP-полной, даже если все литералы в предложениях положительны (MONOTONE), если построенные на графике соединительные предложения с переменными являются плоскими (PLANAR) и каждая переменная содержится ровно в 3 предложениях (CUBIC) (C. Moore и JM Робсон, Проблемы жестких и простых плиток, 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}$

Наконец, мы можем построить гаджеты сдвига и поворота для переноса сигналов в соответствии с лежащим в основе планарным графиком и настройки конечных точек:

$H$$A$

$H /3$$A H / 3$

$H /3$$A H / 3$