Ответ 1
Эта проблема, безусловно, NP-hard, и я могу это доказать. С этой проблемой происходит сокращение от 3-SAT. В частности, это сокращение от 3-SAT к подзадаче этой проблемы, в которой домино 1x3. Могут также быть другие сокращения для других конкретных размеров, но это определенно работает.
По сути, в этом сокращении мы будем использовать позиции домино, чтобы кодировать либо true, либо false. В частности, я собираюсь принять то же обозначение, что и другое решение, то есть сказать, что я буду использовать звездочки, чтобы указать открытые пространства в сетке. Я также буду использовать наборы из трех заглавных букв для представления домино и строчных букв для представления "сигналов", которые являются пробелами, которые могут заполняться или не заполняться в зависимости от состояния системы.
Чтобы внедрить проблему 3-SAT в это пространство, нам понадобится набор того, что я буду называть гаджетами, которые позволяют использовать только определенные состояния. Большинство этих гаджетов будут иметь фиксированное количество домино в них. Исключением будут гаджеты, которые представляют предложения, которые будут иметь один дополнительный домино, если предложение истинно (выполнено), но не тогда, когда оно ложно (неудовлетворено). Мы можем связать эти гаджеты с помощью путей. Вместе это позволит нам построить схему 3-SAT. У нас будет базовое число домино, так как каждый путь и гаджет будут принимать стандартное количество домино, мы можем добавить их, чтобы получить базовое число k, а затем каждый гаджет предложения может иметь один дополнительный домино, если он истинен, поэтому, если все (и, следовательно, выражение удовлетворено), и есть n предложений, тогда максимальное число домино будет n + k. Если нет, то максимальное число будет меньше n + k. Это основная форма сокращения. Далее я опишу гаджеты и приведу примеры.
Как и в другом ответе, мы будем иметь две позиции, которые кодируют true и false для данной переменной. Итак, я начну с одной плитки, которая может быть в двух возможных местах.
****
Это может быть покрыто одним домино, например
AAA* or *AAA
Очевидно, что это не может быть покрыто двумя домино и покрыть его 0 домино никогда не будет максимальным. Для моих целей мы рассмотрим выступы, чтобы представить значение "ложь" и отсутствие выступа для представления "истина". Таким образом, мы можем рассматривать эту часть как имеющую два сигнала:
x**y
И в этом случае будет покрываться только один из x или y, поэтому мы можем рассматривать сигналы как x и логические, а не x. Для наших целей, в зависимости от того, что покрыто, ложно, в зависимости от того, что не покрывается, это правда. Затем мы можем передавать сигналы просто через прямые изогнутые траектории. Если мы имеем
x*****y
Мы снова получим ровно два домино и получим либо x, либо y, но не оба.
***y
*
*
x
Будет иметь точно такое же поведение. Таким образом, мы можем использовать это для создания длинных и изгибающихся путей длиной, которые являются приращениями 3. Однако не все длины, которые мы, возможно, захотим использовать, - это приращения 3, поэтому нам нужно дополнительное устройство для перемещения на другое расстояние. Я называю это гаджетом для скрипача, и только цель состоит в том, чтобы переместить сигнал на несколько неровных расстояний, чтобы они могли успешно соединиться. Его вход поступает от x, а выход переходит в y, и он просто передает один и тот же сигнал. Это выглядит так:
***y
*
**x
Он всегда содержит ровно два домино и заполняется одним из следующих двух способов:
BBB* ABBB
* A
AAA *AX
Если мы собираемся моделировать 3-SAT, нам нужно больше, чем это. В частности, нам нужен способ моделирования предложений. Для этого у нас есть гаджет, в котором один дополнительный домино может быть упакован, если предложение истинно. Предложение будет истинным, если один или несколько его входов истинны. В этом случае это означает, что мы можем упаковать один дополнительный домино, когда хотя бы один из входов не выступает. Он будет выглядеть следующим образом:
*x*y*
*
z
Если для ясности добавить дополнительный путь к каждому, то он выглядит так:
* *
* *
* *
*****
*
****
Если x, y и z все ложные, тогда у всех будут выступы, и они будут заполнены как это:
A B
C D
C D
*C*D*
*
EEEF
Где остальные домино A, B и F продолжают куда-то вниз. Если хотя бы один из входов является истинным, тогда мы можем упаковать в один дополнительный домино (G) так:
C B A D A B
C D C D C D
C D or C D or C D
GGGD* *CGGG *CGD*
* * G
EEEF EEEF GEEE
Однако, даже если все входы истинны, мы не можем упаковать более чем в один домино. Этот сценарий будет выглядеть следующим образом:
C D
C D
C D
*****
*
*EEE
И как вы можете видеть, мы можем вставить только одно дополнительное домино в пустое пространство, а не два.
Теперь, если бы термины никогда не повторялись, мы бы сделали (или почти сделали). Однако их можно повторить, так что в следующий раз нам нужен разделитель сигналов, так что одна переменная может появиться в несколько терминов. Для этого мы используем следующий гаджет:
y*** ***z
* *
***
***
x
В этом гаджете x есть вход, а y и z - выходы. В этом гаджете мы всегда можем упаковать 5 домино. Если х торчит, чем упаковка, 5 домино всегда потребует покрытия y и z. Если x не выступает, то покрытие y и z не требуется. Упаковка, где x не выступает, выглядит следующим образом:
yAAA BBBz
C D
CED
CED
E
Когда x выступает (мы используем X, чтобы указать конец домино, выступающего в пространство x), максимальная упаковка обязательно охватывает как y, так и z:
AAAC DBBB
C D
C*D
EEE
X
Я займу минутку, чтобы отметить, что можно будет упаковать это с пятью домино, когда х не будет выступать таким образом, чтобы либо y, либо z выступали. Однако это приведет к тому, что термины, которые могут быть истинными (не выступающими), становятся ложными (выступающими). Разрешить некоторые термины (а не переменные, но фактические термины в статьях) различать по значению только путем ненужного ложного обращения, никогда не приведет к тому, что он сможет удовлетворять иначе неудовлетворительному выражению. Если бы наше 3-SAT-выражение было (x | y | z) и (! X | y |! Z), что позволило бы как x, так и x быть ложными, это только усложняло бы ситуацию. Если бы мы допустили, чтобы оба конца чего-то были истинными, это привело бы к неправильным решениям, но мы не делаем этого в этой схеме. Чтобы скомпоновать его с точки зрения нашей конкретной проблемы, излишнее излишнее никогда не приведет к тому, что большее количество домино сможет быть упаковано позже по линии.
С путями и этими тремя гаджетами мы теперь можем решить планарный 3-SAT, который будет подзадачей 3-SAT, если мы рисуем график, где члены и предложения являются вершинами, и есть ребро между каждым термин и каждое предложение, которое содержит этот термин, что граф является планарным. Я считаю, что планарный 3-SAT, вероятно, NP-жесткий, потому что плоский 1-в-3-SAT есть, но в противном случае мы можем использовать гаджеты для пересечения сигнала. Но это действительно довольно сложно (если кто-то видит более простой способ, пожалуйста, дайте мне знать), так что сначала я собираюсь сделать пример решения планарного 3-SAT с этой системой.
Таким образом, простая плоская задача 3-SAT будет (x | y | z) и (! x | y |! z). Очевидно, что это выполнимо, используя любое присваивание, где y истинно или несколько других назначений. Таким образом мы построим нашу проблему с домино:
*******
* *
* *
**** ***
* *
*** ****
* *
* *
* ******* *
* * * *
* * * *
*z*x* *****
* *
**** ****
* *
***
***
*
*
*
y
Обратите внимание, что нам нужно было использовать скрипачей наверху, чтобы правильно перенести вещи, иначе это было бы значительно менее сложно.
Добавляя общее количество домино из гаджетов и дорожек, у нас есть 1 сплиттер (5 домино), два скрипача (по 2 домино каждый) и всего 13 регулярных путей, в общей сложности 5 + 2 * 2 + 13 = Гарантировано 22 домино, даже если положения не могут быть удовлетворены. Если они могут быть, тогда у нас будет еще 2 домино, которые могут быть заполнены в общей сложности 24. Одна оптимальная упаковка с 24 домино состоит в следующем:
QRRRSSS
Q T
Q T
OPPP *UT
O U
*ON UVVV
N W
N W
M IIIJJJK W
M H K X
M H K X
*zGH* LLLX*
G *
GEEE FFF*
B D
BCD
BCD
C
A
A
A
Этот тайлинг содержит 24 домино, поэтому мы можем знать, что исходное выражение является выполнимым. В этом случае тайлинг соответствует y и x true и z false. Обратите внимание, что это не единственное мозаичное (а не единственное удовлетворительное назначение булевых значений), но нет другого тайлирования, которое увеличит количество фрагментов за пределами 24, поэтому это максимальная разбивка. (Если вы не хотите считать все домино, вы можете заметить, что я использовал каждую букву, кроме Y и Z.)
Если максимальная черепица содержала 22 или 23 домино, то мы знали бы, что одно из предложений не было выполнено (GGG и/или LLL-домино не могли быть размещены), и, следовательно, мы знали бы, что оригинал выражение не было выполнено.
Чтобы быть уверенным, что мы можем это сделать, даже если плоский 3-SAT не является NP-жестким, мы можем создать гаджет, который позволяет пересекать пути. Этот гаджет, к сожалению, очень большой и сложный, но это самый маленький, который я смог выяснить. Сначала я опишу фрагменты, а затем весь гаджет.
Часть 1: точка кроссовера. x и y - входы. a, b и c - выходы. Они должны быть объединены с использованием других гаджетов, чтобы фактически передавать x и y на противоположную сторону друг от друга.
***c
*
***
* *
* *
* *
***
***
ax*yb
Этот гаджет всегда будет соответствовать ровно 7 домино. Существует четыре возможных комбинаций ввода. Если ни один вход не выступает (оба являются истинными), ни один выход не будет выступать, и он будет заполнен, как показано ниже (tt1) или (tt2). Если выдается только вход x, тогда будет выступать только c, как в (ft) ниже. Если выдается только вход y, то либо выход a, либо c будет выступать так же, как и в (tf) ниже. И если вход x и y оба выступают, то выход c выступает так же, как в (ff) ниже.
(tt) AAAc (ft) AAAc (tf) AAAc (ff) BAAA
* * * B
BBB BBB BBB CBD
C D C D C D C D
C D C D C D C D
C D C D C D E G
EEE EEE EEE EFG
FFF FFF FFF EFG
aGGGb aXGGG GGGYb aXFYb
Я не включил возможность того, что в сценариях (ft) или (tf), чтобы c мог быть покрыт вместо a или b. Это возможно в рамках этого гаджета, но в сочетании с другими гаджетами, чтобы сформировать полный кроссовер, если бы это было так, это не привело бы к тому, что большее количество предложений было бы удовлетворено, поэтому мы можем исключить его. Имея это в виду, мы можем заметить, что в этом случае значение входа x равно значению b и c, а вход y равен значению a и c (обратите внимание, что это было бы логично или, скорее, чем логические, и если выступы считались истинными, а не ложными). Таким образом, нам просто нужно разделить c, а затем использовать логический и гаджет для соединения соединить значения c с a и b соответственно, и мы сможем успешно завершить наш крест.
Логический и наш самый простой гаджет до сих пор, и он выглядит так:
****
*
x*y
На самом деле вы можете заметить, что он встроен в верхнюю часть гаджета точки кроссовера. Этот гаджет всегда будет содержать ровно 2 домино. Один из них будет наверху, чтобы служить выходом. Другой служит в качестве переключателя, который будет ориентирован по горизонтали, только если оба x и y являются истинными (не выступающими) и вертикально ориентированными в противном случае, как мы можем видеть на следующих диаграммах:
BBB* ABBB ABBB ABBB
* A A A
AAA XAy xAY XAY
Таким образом, мы можем завершить кроссовер, разделив c, а затем добавив два из этих ворот: один для a и c и один для b и c. Объединение всего этого требует также добавления некоторых гаджетов скрипача и выглядит так:
******* ****
* * * *
* *** *
*** *** ***
* * *
**** * ****
* * *
* **** *
*** * ***
* *** *
**** * * ****
y * * * * x
* * * * * *
* **** *** **** *
*** *** ***
**********x*y*************
Я не собираюсь заполнять примеры для этого. Вам нужно будет сделать это сами, если вы хотите увидеть это в действии. Итак, ура! Теперь мы можем делать произвольные 3-SAT. Я должен сделать минутку, чтобы заметить, что это будет полиномиальное преобразование времени, потому что даже в худшем случае мы можем просто создать большую сетку со всеми переменными и их противоположностями вдоль вершины и всеми членами на стороне и сделать O (n ^ 2). Таким образом, существует простой алгоритм с полиномиальным временем для выкладки всего этого, а максимальный размер преобразованной задачи является полиномиальным по размеру проблемы ввода. Что и требовалось доказать.
Изменить примечание: После того, как Том Сиргедас отлично справился с поиском ошибки в гаджет-сплиттере, я внесла некоторые изменения в ответ. По существу, мой старый сплиттер выглядел так и мог быть упакован с 6, когда х не выступал (а не 5, я намеревался), как это:
y*** ***z AAAC DBBB
* * C D
*** C*D
*** EEE
*x* FFF
Поэтому я пересмотрел его, удалив два пространства по обе стороны от x. Это устраняет шесть упаковок домино, сохраняя при этом 5-домино-упаковку, в которой y и z раскрываются при обнаружении x.