Для какого k PLANAR NAE k-SAT в P?

23

Задача «Не все равно k -SAT» (NAE k -SAT), учитывая набор C предложений над набором X булевых переменных, так что каждое предложение содержит не более k литералов, спрашивает, существует ли истинное присвоение переменных таким образом, чтобы каждое предложение содержит, по крайней мере, один истинный и, по крайней мере, один ложный литерал.

ПЛАНАРНАЯ задача NAE k -SAT является ограничением NAE k -SAT для тех случаев, когда двудольный граф инцидентности C и X (т. Е. Граф частей C и X с ребром между xX и cC если и только если x или x¯ принадлежит c ), является плоской.

Известно, что 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-полное?kkk4k

Флоран Фуко
источник

Ответы:

23

PLANAR NAE -SAT находится в P для всех значений k .kk

Причина в том, что мы можем уменьшить PLANAR NAE -SAT до PLANAR NAE 3 -SAT. Пусть ϕ будет экземпляром PLANAR NAE k -SAT, и пусть ϕ и v C , тогда как C 2k3ϕkϕ содержит предложение с литералами 1 , 2 , , k . Введите новую переменную v C и замените C двумя предложениями NAE C 1 и C 2 . C 1 содержит 3 литерала 1 , 2C1,2,,kvCCC1C2C1312vCC2 содержит литерал ˉ v C , 3 , 4 , , k . Легко видеть, что C выполнима тогда и только тогда, когда C 1C 2 , и преобразование сохраняет планарность. Теперь мы можем неоднократно применять эту процедуру к предложениям, чтобы в конечном итоге получить экземпляр ϕ NAE 3 -SAT по желанию.k1v¯C,3,4,,kCC1C2ϕ3

Арнаб
источник
1
Отличный ответ. Было ли это уже известно?
Серж Гасперс
1
Похоже, что это сокращение «работает» даже без плоской оговорки, поэтому оно, вероятно, «известно»
Суреш Венкат
@ Серж, я уверен, что так и было, но я не знаю ссылки.
Арнаб
6
Это стандартное сокращение, которое также работает для «обычного» SAT. Вы можете найти его, например, в книге Сипсера «Введение в теорию вычислений» и во многих других.
5501