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

11

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

  • вход: сетка с несколькими отмеченными квадратами, порог , максимальная площадьT N A NMTNAN
  • Выход: наибольшая возможная площадь множества непересекающихся прямоугольников с целыми координатами в общей таким образом, что каждый прямоугольник включает , по меньшей мере , отмеченные квадраты и каждый прямоугольник имеет область в большинстве .Т АMTA

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

Мы можем четко перефразировать эту проблему в решение проблемы, добавив дополнительный ввод и пусть ответ будет "есть ли набор непересекающихся прямоугольников, удовлетворяющих условиям, общая площадь которых не менее квадратов". nnNn

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

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

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

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

aaAa
bBcc
bbCc
bbcc

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

XXX
.X.
...

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

AAA
.X.
...

или же

XBX
.B.
.b.

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

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

a3nm
источник

Ответы:

10

Это эскиз сокращения от MONOTONE CUBIC PLANAR 1-3 SAT:


φ=C1C2...CmCjCj=(j,1j,2j,3)
φCj содержит ровно один истинный литерал.

Проблема остается NP-полной, даже если все литералы в предложениях положительны (MONOTONE), если построенные на графике соединительные предложения с переменными являются плоскими (PLANAR) и каждая переменная содержится ровно в 3 предложениях (CUBIC) (C. Moore и JM Робсон, Проблемы жестких и простых плиток, Discrete Comput. Geom. 26 (2001), 573-590.).

T=3,A=6

A+

введите описание изображения здесь

xixi=TRUExi=FALSE

введите описание изображения здесь

CjLя,1,Lя,2,Lя,3

введите описание изображения здесь

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

введите описание изображения здесь

ЧАСA

ЧАС/3AЧАС/3

ЧАС/3AЧАС/3

Вор
источник