Не все равно 3-выполнимость - Not-all-equal 3-satisfiability - Wikipedia
В вычислительная сложность, не все равно 3-выполнимость (NAE3SAT) является НП-полный вариант Проблема логической выполнимости, часто используется в доказательствах NP-полноты.[1]
Определение
Нравиться 3-выполнимость, экземпляр проблемы состоит из набора Булевы переменные и набор предложений, каждое из которых объединяет три переменные или отрицания переменных. Однако, в отличие от 3-выполнимости, которая требует, чтобы каждое предложение имело хотя бы одно истинное логическое значение, NAE3SAT требует, чтобы три значения в каждом предложении не были все равны друг другу (другими словами, по крайней мере одно истинно, и по крайней мере один ложный).[2]
Твердость
NP-полнота NAE3SAT может быть доказана снижение из 3-выполнимости.[2]
Проблема остается NP-полной, когда все предложения монотонны (что означает, что переменные никогда не инвертируются), Теорема дихотомии Шефера.[3]Монотонный NAE3SAT также можно интерпретировать как экземпляр установить задачу разделения, или как обобщение двудольность графа тестирование до 3-х униформ гиперграфы: он спрашивает, можно ли раскрасить вершины гиперграфа в два цвета так, чтобы ни одно гиперребро не было одноцветным. Более того, это NP-сложно найти раскраски 3-однородных гиперграфов с любым постоянным числом цветов, даже если существует 2-раскраска.[4]
Легкие случаи
В отличие от 3SAT, некоторые варианты NAE3SAT, в которых графики, представляющие структуру переменных и предложений, планарные графы можно решить в полиномиальное время. В частности, это верно, когда существует планарный граф с одной вершиной на переменную, одной вершиной на предложение, ребром для каждой инцидентности предложений переменных и циклом ребер, соединяющих все вершины переменных.[5]
Рекомендации
- ^ Морет (1988): "Среди опубликованных доказательств NP-полноты можно найти больше сокращений от 3-Satisfability (3SAT для краткости) и его основных вариантов, One-in-three-3SAT (1in3SAT) и Not-all-equal 3SAT (NAE3SAT), чем от любой другой NP-полной задачи ".
- ^ а б Мур, Кристофер; Мертенс, Стефан (2011), «Нарушение симметрии и НАЭСАТ», Природа вычислений, Oxford University Press, стр. 133–138, ISBN 9780199233212
- ^ Шефер, Томас Дж. (1978), «Сложность проблем выполнимости», Proc. Десятый симпозиум ACM по теории вычислений (STOC '78), Нью-Йорк: ACM, стр. 216–226, МИСТЕР 0521057
- ^ Динур, Ирит; Регев, Одед; Смит, Клиффорд (2005), "Трудность 3-однородной раскраски гиперграфа", Комбинаторика, 25 (5): 519–535, Дои:10.1007 / s00493-005-0032-4, МИСТЕР 2176423
- ^ Морет, Б.М. (Июнь 1988 г.), «Планар NAE3SAT находится в P», Новости ACM SIGACT, 19 (2): 51–54, Дои:10.1145/49097.49099