Задача «Не все равно -SAT» (NAE -SAT), учитывая набор предложений над набором булевых переменных, так что каждое предложение содержит не более литералов, спрашивает, существует ли истинное присвоение переменных таким образом, чтобы каждое предложение содержит, по крайней мере, один истинный и, по крайней мере, один ложный литерал.
ПЛАНАРНАЯ задача NAE -SAT является ограничением NAE -SAT для тех случаев, когда двудольный граф инцидентности и (т. Е. Граф частей и с ребром между и если и только если или принадлежит ), является плоской.
Известно, что NAE 3-SAT является NP-полной (Garey and Johnson, Computers and Intractability; Руководство по теории NP-полноты), но PLANAR NAE 3-SAT находится в P (см. Планарная NAE3SAT в P, B Морет, Новости ACM SIGACT, том 19, выпуск 2, лето 1988 г. - к сожалению, у меня нет доступа к этой статье).
Является ли PLANAR NAE -SAT в P для некоторого ? Есть ли значение для которого было показано, что оно NP-полное?k