Определение плоскости 3-SAT

10

Каково стандартное определение Planar 3-SAT? Я видел много разных определений. Какая оригинальная статья определила ее и доказала, что она является NP-полной?

user24175
источник
2
Что вас смущает в результатах?
Ниль де Бёдрап,
Я вижу разные определения, как некоторые говорят: двудольный граф между предложениями и литералами должен быть плоским (я не знаю под литералами, они означают только x_i или оба x_i и его отрицание, я имею в виду, я не знаю, каковы их График гаджета именно здесь?). Некоторые другие определяют два типа для него: только двудольные ребра между предложениями и литералами или эти плюсы (x_i, ~ x_i). Или кто-то другой говорит, что приведенный выше график плюс (x_i, x_ {i + 1}) 's? Я даже не могу найти оригинальную статью, опубликованную на нем? В принципе, я не могу найти хорошую ссылку с идеальным определением для него?
user24175
4
Первоначальная ссылка: Д. Лихтенштейн, «Плоские формулы и их использование» (1982) ; но есть много небольших вариаций, которые все еще являются NP-полными (доказательство NPC большинства из них легко).
Марцио Де Биаси
1
@ Marzio De Biasi Спасибо большое! Но, основываясь на этой паре, планарная 3-SAT - это случай, когда двудольный граф между предложениями о том, что литералы (только x_i не являются их отрицаниями), является плоским. Правильно? Мы можем легко завершить случай, когда мы включаем также отрицание x_i, просто добавив грань между ними, не нарушая планарность, верно?
user24175
1
Икся+Икся-Икся

Ответы:

12

На http://courses.csail.mit.edu/6.890/fall14/scribe/lec7.pdf есть хорошая подборка определений связанных NP-полных плоских задач выполнимости.

Один из них, плоский монотонный 3-сат, позволяет разделить каждый терминал на положительный и отрицательный, причем клеммы расположены вдоль линии с положительной частью на одной стороне линии и отрицательной частью на другой стороне линии. Предложения имеют только положительные или только отрицательные терминалы и размещаются на положительной или отрицательной стороне линии соответственно.

Дэвид Эппштейн
источник