Планар SAT - Planar SAT

Пример плоской задачи SAT. Красные края соответствуют неинвертированным переменным, а черные края соответствуют инвертированным переменным.

В Информатика, то плоская задача 3-выполнимости (сокращенно ПЛАНАР 3SAT) является расширением классической Булева проблема 3-выполнимости к планарный график заболеваемости. Другими словами, он спрашивает, могут ли переменные данной булевой формулы, график заболеваемости состоящий из переменных и предложений может быть встроенный на самолет - могут быть последовательно заменены значениями ИСТИНА или ЛОЖЬ таким образом, чтобы формула оценивается как ИСТИНА. Если это так, формула называется удовлетворительный. С другой стороны, если такого присвоения не существует, функция, выражаемая формулой, имеет вид ЛОЖНЫЙ для всех возможных назначений переменных и формула неудовлетворительный. Например, формула "а И НЕТ б"выполнимо, потому что можно найти значения а = ИСТИНА и б = FALSE, что делает (а И НЕТ б) = ИСТИНА. В отличие, "а И НЕТ а"неудовлетворительно.

Нравиться 3СБ, PLANAR-SAT - это НП-полный, и обычно используется в сокращение.

Определение

А планарный граф - граф, который можно нарисовать на плоскости таким образом, чтобы никакие два его ребра не пересекались. Каждую задачу 3SAT можно преобразовать в график заболеваемости следующим образом: Для каждой переменной ${\displaystyle v_{i}}$, графу соответствует один ${\displaystyle v_{i}}$, и для каждого пункта ${\displaystyle c_{j}}$, графу соответствует одна вершина ${\displaystyle c_{j}.}$Создаем край ${\displaystyle (v_{i},c_{j})}$ между переменной ${\displaystyle v_{i}}$и пункт ${\displaystyle c_{j}}$ в любое время ${\displaystyle v_{i}}$ или же ${\displaystyle {\bar {v_{i}}}}$ в ${\displaystyle c_{j}}$. Мы различаем положительные и отрицательные литералы, используя окраска краев.

Planar 3SAT - это подмножество 3SAT, в котором график заболеваемости переменных и клозов Булево формула плоский. Это важно, потому что это ограниченный вариант, и он все еще является NP-полным. Многие задачи (например, игры и головоломки) не могут представлять собой неплоские графы. Таким образом, Planar 3SAT дает возможность доказать, что эти игры NP-трудны.

Доказательство NP-полноты

(Следующий набросок доказательства следует за доказательством Д. Лихтенштейна.)^[1]

Банально, PLANAR 3SAT находится в НП. Таким образом, достаточно показать, что это NP-жесткий за счет сокращения с 3СБ.

Сначала нарисуйте график заболеваемости по формуле 3SAT. Поскольку никакие две переменные или предложения не связаны, результирующий граф будет двудольный. Полученный граф не может быть плоским. Замените каждое пересечение краев показанным гаджетом кроссовера здесь.^{[требуется разъяснение ]} Однако этот рисунок приводит к незначительной ошибке - некоторые пункты содержат 4 переменные, а некоторые - только 2 переменные, поэтому предпосылки 3SAT не соблюдаются в точности в показанном гаджете. Этот сбой легко исправить: для предложения, содержащего только 2 переменные, либо создайте параллельные ребра от одной переменной к предложению, либо создайте отдельную ложную переменную для включения в ограничение.

Для предложения с четырьмя переменными возьмите сокращение с 4SAT до 3SAT.^{[требуется разъяснение ]} для создания гаджета, который включает в себя введение дополнительной переменной, для которой установлено значение false, которое указывает, содержится ли в левой или правой части исходного предложения соответствующий литерал. На этом сокращение завершено.

Варианты и связанные с ними проблемы

• Планарный прямолинейный 3SAT: Каждая переменная представляет собой горизонтальный сегмент на Икс-axis, а каждое предложение представляет собой горизонтальный сегмент над Икс- ось с вертикальными связями с 3 переменными, которые она включает в Икс-ось. Связи могут быть как положительными, так и отрицательными. Эта проблема является NP-полной.^[2]
• Планарный монотонный прямолинейный 3SAT: Это вариант плоского прямолинейного 3SAT, в котором все положительные элементы находятся над Икс-axis и все отрицательные предложения находятся ниже оси x. Эта задача также является NP-полной.^[3]
• Планар 1-в-3SAT: Это планарный эквивалент 1-в-3СБ. Он также является NP-полным.^[4]
• Планар NAE 3SAT: Эта задача является плоским эквивалентом NAE 3SAT. Удивительно, но ее можно решить за полиномиальное время.^[5]

Скидки

Шакашака

Шакашака логическая настольная игра-головоломка, разработанная издателем Николи. Задача состоит в том, чтобы заполнить белые квадраты в заданной сетке узором из треугольников так, чтобы каждая белая область в итоговой сетке имела прямоугольную форму. Кроме того, каждый черный квадрат в сетке, отмеченный номером, должен быть ортогонально смежный на указанное количество треугольников. Было доказано, что он является NP-полным за счет сокращения от Planar 3SAT^[6]

Плоское складывание цепей с фиксированным углом

Это проблема определения того, имеет ли многоугольная цепь с фиксированными длинами ребер и углами плоскую конфигурацию без пересечений. Было доказано, что это сильно NP-жесткий через редукцию от плоского монотонного прямолинейного 3SAT.^[7]

Триангуляция минимального веса

Это проблема поиска триангуляция минимальной общей длины кромки. Доказано, что вариант решения этой проблемы является NP-полным за счет сокращения варианта Planar 1-in-3SAT.^[8]

Рекомендации

1. Лихтенштейн, Дэвид (1982-05-01). «Планарные формулы и их использование». SIAM Журнал по вычислениям. 11 (2): 329–343. Дои:10.1137/0211025. ISSN  0097-5397.
2. Рагхунатан, Арвинд; Кнут, Дональд Э. (1992). «Проблема совместимых представителей». SIAM J. Дискретная математика. 5 (3): 422–427. arXiv:cs / 9301116. Bibcode:1993cs ........ 1116K. Дои:10.1137/0405033.
3. Де Берг, Марк; Хосрави, Амирали (2010). «Оптимальные двоичные разбиения пространства на плоскости». Вычислительная техника и комбинаторика. Конспект лекций по информатике. 6196. С. 216–225. Дои:10.1007/978-3-642-14031-0_25. ISBN  978-3-642-14030-3.
4. Дайер, M.E; Frieze, AM (июнь 1986 г.). «Планарная 3DM является NP-полной». Журнал алгоритмов. 7 (2): 174–184. Дои:10.1016/0196-6774(86)90002-7.
5. Морет, Б. М. Э. (июнь 1988 г.). «Планар NAE3SAT находится в P». Новости SIGACT. 19 (2): 51–54. Дои:10.1145/49097.49099. ISSN  0163-5700.
6. Demaine, Erik D .; Окамото, Ёсио; Уэхара, Рюхей; Уно, Юши (2014), «Вычислительная сложность и целочисленная модель программирования Шакашаки» (PDF), Сделки IEICE по основам электроники, связи и компьютерных наук, E97-A (6): 1213–1219, Bibcode:2014IEITF..97.1213D, Дои:10.1587 / transfun.E97.A.1213, HDL:10119/12147
7. Demaine, Erik D .; Айзенстат, Сара (2011). Дене, Франк; Яконо, Джон; Мешок, Йорг-Рюдигер (ред.). «Выпрямление цепей с фиксированным углом - сильно NP-трудное дело». Алгоритмы и структуры данных. Конспект лекций по информатике. Springer Berlin Heidelberg. 6844: 314–325. Дои:10.1007/978-3-642-22300-6_27. ISBN  9783642223006.
8. Мульцер, Вольфганг; Роте, Гюнтер (май 2008 г.). «Триангуляция минимального веса NP-сложна». J. ACM. 55 (2): 11:1–11:29. Дои:10.1145/1346330.1346336. ISSN  0004-5411.