Не все-равная 3-выполнимость

По вычислительной сложности не все равные 3-выполнимости ( NAE3SAT ) представляют собой NP-полный вариант булевой проблемы выполнимости , часто используемый в доказательствах NP-полноты. ^[1]

Определение

Как и 3-выполнимость , экземпляр задачи состоит из набора логических переменных и набора предложений, каждое из которых объединяет три переменные или отрицания переменных. Однако в отличие от 3-выполнимости, которая требует, чтобы каждое предложение имело хотя бы одно истинное логическое значение, NAE3SAT требует, чтобы три значения в каждом предложении не были равны друг другу (другими словами, по крайней мере одно истинно, и по крайней мере одно ложное). ^[2]

Твердость

NP-полнота NAE3SAT может быть доказана путем редукции к 3-выполнимости (3SAT). ^[2] Сначала несимметричный 3SAT сводится к симметричному NAE4SAT путем добавления общего фиктивного литерала. $s$ к каждому пункту, то NAE4SAT сводится к NAE3SAT путем разделения пунктов, как при сокращении общих $k$ -соответствие 3SAT.

Более подробно экземпляр 3SAT $\Phi =\bigwedge _{i=1}^{m}(l_{i,1}\vee l_{i,2}\vee l_{i,3})$ (где $l_{i,j}$ являются произвольными литералами) сводится к экземпляру NAE4SAT $\Psi =\bigwedge _{i=1}^{m}(l_{i,1},l_{i,2},l_{i,3},s)$ где $s$ это новая переменная. Удовлетворительное задание для $\Phi$ становится удовлетворяющим заданием для $\Psi$ установив $s=0$ . И наоборот, удовлетворительное задание с $s=0$ для $\Psi$ должен иметь хотя бы еще один истинный литерал в каждом предложении и, таким образом, быть удовлетворительным присваиванием для $\Phi$ . Наконец-то удовлетворительное задание с $s=1$ для $\Psi$ может из-за симметрии $0$ и $1$ перевернуть, чтобы получить удовлетворительное задание с $s=0$ .

NAE3SAT остается NP-полным, когда все предложения монотонны (что означает, что переменные никогда не отменяются), согласно теореме Шефера о дихотомии . ^[3]Монотонный NAE3SAT также можно интерпретировать как пример проблемы разделения множества или как обобщение. для проверки двудольности графа 3-однородных гиперграфов вершины гиперграфа : он спрашивает, можно ли раскрасить в два цвета так, чтобы ни одно гиперребро не было монохроматическим. Более того, NP-трудно найти раскраски 3-однородных гиперграфов в любое постоянное число цветов, даже если 2-раскраска существует. ^[4]

Простые случаи

В отличие от 3SAT, некоторые варианты NAE3SAT, в которых графы, представляющие структуру переменных и предложений, являются плоскими графами, могут быть решены за полиномиальное время . В частности, это верно, когда существует планарный граф с одной вершиной на переменную, одной вершиной на предложение, ребром для каждой инцидентности переменной и предложения и циклом ребер , соединяющим все вершины переменных. ^[5]

Ссылки

^ Морет (1988) : «Среди опубликованных доказательств NP-полноты можно найти больше сокращений от 3-выполнимости (сокращенно 3SAT) и ее основных вариантов, 3SAT «один из трех» (1in3SAT) и 3SAT «не все равны». (NAE3SAT), чем от любой другой NP-полной задачи».
^ Jump up to: ^а ^б Мур, Кристофер ; Мертенс, Стефан (2011), «Нарушение симметрии и NAESAT» , Природа вычислений , Oxford University Press, стр. 133–138, ISBN 9780199233212
^ Шефер, Томас Дж. (1978), «Сложность проблем выполнимости», Proc. Десятый симпозиум ACM по теории вычислений (STOC '78) , Нью-Йорк: ACM, стр. 216–226, MR 0521057.
^ Динур, Ирит ; Регев, Одед ; Смит, Клиффорд (2005), «Твердость 3-равномерной раскраски гиперграфа», Combinatorica , 25 (5): 519–535, doi : 10.1007/s00493-005-0032-4 , MR 2176423
^ Море, BME (июнь 1988 г.), «Планарный NAE3SAT находится в P», ACM SIGACT News , 19 (2): 51–54, doi : 10.1145/49097.49099 , S2CID 17219595

[moqo-1] Морет (1988) : «Среди опубликованных доказательств NP-полноты можно найти больше сокращений от 3-выполнимости (сокращенно 3SAT) и ее основных вариантов, 3SAT «один из трех» (1in3SAT) и 3SAT «не все равны». (NAE3SAT), чем от любой другой NP-полной задачи».

[noc-2] Jump up to: ^а ^б Мур, Кристофер ; Мертенс, Стефан (2011), «Нарушение симметрии и NAESAT» , Природа вычислений , Oxford University Press, стр. 133–138, ISBN 9780199233212

[schaefer-3] Шефер, Томас Дж. (1978), «Сложность проблем выполнимости», Proc. Десятый симпозиум ACM по теории вычислений (STOC '78) , Нью-Йорк: ACM, стр. 216–226, MR 0521057.

[drs-4] Динур, Ирит ; Регев, Одед ; Смит, Клиффорд (2005), «Твердость 3-равномерной раскраски гиперграфа», Combinatorica , 25 (5): 519–535, doi : 10.1007/s00493-005-0032-4 , MR 2176423

[moret-5] Море, BME (июнь 1988 г.), «Планарный NAE3SAT находится в P», ACM SIGACT News , 19 (2): 51–54, doi : 10.1145/49097.49099 , S2CID 17219595

[1]

[2]

[3]

[4]

[5]