Теорема Шефера о дихотомии

В теории сложности вычислений разделе информатики , теорема дихотомии Шефера , доказанная Томасом Джеромом Шефером , устанавливает необходимые и достаточные условия, при которых конечный набор S отношений , в булевой области дает полиномиальное время или NP-полные задачи, когда отношения из S используются для ограничения некоторых пропозициональных переменных . ^{[ 1 ]} Это называется теоремой дихотомии , потому что сложность проблемы, определяемой S, либо находится в P, либо является NP-полной, в отличие от одного из классов промежуточной сложности , о существовании которого известно (при условии, что P ≠ NP ) по теореме Ладнера .

Особые случаи теоремы дихотомии Шефера включают NP-полноту SAT ( булева проблема выполнимости ) и два ее популярных варианта SAT 1-в-3 и не все равные 3SAT (часто обозначаемые NAE-3SAT). Фактически, для этих двух вариантов SAT теорема дихотомии Шефера показывает, что их монотонные версии (где отрицание переменных не допускается) также являются NP-полными.

Оригинальная презентация

Шефер определяет проблему принятия решения , которую он называет проблемой обобщенной выполнимости для S (обозначаемой SAT( S )), где $S=\{R_{1},\ldots ,R_{m}\}$ представляет собой конечный набор отношений в бинарной области $\{0,1\}$ . Примером задачи является S -формула, т.е. совокупность ограничений вида $R_{j}(x_{i_{1}},\dots ,x_{i_{n}})$ где $R_{j}\in S$ и $x_{i_{j}}$ являются пропозициональными переменными. Проблема состоит в том, чтобы определить, является ли данная формула выполнимой, другими словами, можно ли присвоить переменным такие значения, чтобы они удовлетворяли всем ограничениям, заданным отношениями из S .

Шефер идентифицирует шесть классов наборов булевых отношений, для которых SAT( S ) находится в P, и доказывает, что все остальные наборы отношений порождают NP-полную задачу. Конечный набор отношений S над булевой областью определяет проблему вычислимой выполнимости за полиномиальное время, если выполняется любое из следующих условий:

все отношения, которые не являются постоянно ложными, истинны, когда все их аргументы истинны;
все отношения, которые не являются постоянно ложными, истинны, когда все его аргументы ложны;
все отношения эквивалентны соединению бинарных предложений ;
все отношения эквивалентны соединению предложений Хорна ;
все отношения эквивалентны соединению предложений двойного Хорна;
все отношения эквивалентны конъюнкции аффинных формул. ^{[ 2 ]}

В противном случае задача SAT( S ) является NP-полной.

Современная презентация

Современное, упрощенное изложение теоремы Шефера дано в объяснительной статье Хьюби Чена. ^{[ 3 ]}^{[ 4 ]} Говоря современным языком, проблема SAT( S ) рассматривается как проблема удовлетворения ограничений в булевой области . В этой области принято обозначать множество отношений через Γ, а проблему решения, определяемую Γ, как CSP(Γ).

В этом современном понимании используется алгебра , в частности, универсальная алгебра . Согласно теореме Шефера о дихотомии, наиболее важным понятием универсальной алгебры является понятие полиморфизма. Операция $f:D^{m}\to D$ является полиморфизмом отношения $R\subseteq D^{k}$ если для любого выбора из m кортежей $(t_{11},\dotsc ,t_{1k}),\dotsc ,(t_{m1},\dotsc ,t_{mk})$ из R , то кортеж, полученный из этих m кортежей путем применения f по координатам, т.е. $(f(t_{11},\dotsc ,t_{m1}),\dotsc ,f(t_{1k},\dotsc ,t_{mk}))$ в Р. , находится То есть операция f является полиморфизмом R, R замкнут относительно f : применение f к любым кортежам в R дает еще один кортеж внутри R. если Говорят, что множество отношений Γ имеет полиморфизм f , если каждое отношение в Γ имеет f как полиморфизм. Это определение позволяет алгебраическую формулировку теоремы дихотомии Шефера.

Пусть Γ — конечный язык ограничений в булевой области. Задача CSP(Γ) разрешима за полиномиальное время, если Γ имеет одну из следующих шести операций в качестве полиморфизма:

постоянная унарная операция 1;
постоянная унарная операция 0;
двоичная операция И ∧;
двоичная операция ИЛИ ∨;
операция тройного большинства $\operatorname {Majority} (x,y,z)=(x\wedge y)\vee (x\wedge z)\vee (y\wedge z);$
операция тройного меньшинства $\operatorname {Minority} (x,y,z)=x\oplus y\oplus z.$

В противном случае задача CSP(Γ) является NP-полной.

В этой формулировке легко проверить, выполнено ли какое-либо из условий слаженности.

Свойства полиморфизмов

Учитывая набор отношений Γ, существует удивительно тесная связь между его полиморфизмами и вычислительной сложностью CSP(Γ).

Отношение R называется примитивным положительно определимым или кратким pp-определимым из отношения набор Γ отношений, если р ( v ₁ , ... , v _k ) ⇔ ∃ Икс ₁ ... Икс _м . C имеет место для некоторой комбинации C ограничений из Γ и уравнений над переменными { v ₁ ,..., v _k , x ₁ ,..., x _m }. Например, если Γ состоит из троичного отношения nae ( x , y , z ), выполняющего условие, если x , y , z не все равны, и R ( x , y , z ) равно x ∨ y ∨ z , то R может быть pp-определено как R ( Икс , y , z ) ⇔ ∃ а . nae (0, x , a ) ∧ nae ( y , z ,¬ a ); это сокращение было использовано для доказательства того, что NAE-3SAT является NP-полным. Множество всех отношений, pp-определимых из Γ, обозначается ≪Γ≫. Если Γ' ⊆ ≪Γ≫ для некоторых конечных множеств ограничений Γ и Γ', то CSP(Γ') сводится к CSP(Γ). ^{[ 5 ]}

Для заданного множества отношений Γ Pol (Γ) обозначает множество полиморфизмов Γ. И наоборот, если O — набор операций, то Inv ( O ) обозначает набор отношений, в которых все операции из O являются полиморфизмом. Pol и Inv вместе образуют антитонную связь Галуа . Для любого конечного множества отношений Γ в конечной области имеет место соотношение ≪Γ≫ = Inv ( Pol (Γ)), т. е. множество отношений, pp-определимых из Γ, может быть получено из полиморфизмов Γ. ^{[ 6 ]} Более того, если Pol (Γ) ⊆ Pol (Γ') для двух конечных множеств отношений Γ и Γ', то Γ' ⊆ ≪Γ≫ и CSP(Γ') сводится к CSP(Γ). Как следствие, два набора отношений, имеющие одинаковые полиморфизмы, приводят к одинаковой вычислительной сложности. ^{[ 7 ]}

Обобщения

Позже анализ был уточнен: CSP(Γ) разрешима либо в co-NLOGTIME, либо в L-полном , NL-полном , ⊕L-полном, P-полном или NP-полном, а учитывая Γ, можно принять решение в полиномиальном время, который из этих случаев имеет место. ^{[ 8 ]}

Теорема Шефера о дихотомии также была обобщена для использования пропозициональной логики графов вместо булевой логики. ^{[ 9 ]}

Связанная работа

Если задача состоит в подсчете количества решений, которое обозначается #CSP(Γ), то для бинарной области существует аналогичный результат Крейньу и Германа. ^{[ 10 ]} В частности, конечное множество отношений S в булевой области определяет проблему вычислимой выполнимости с полиномиальным временем, если каждое отношение в S эквивалентно конъюнкции аффинных формул. ^{[ 2 ]}

Для более крупных областей необходимое условие выполнимости за полиномиальное время было дано Булатовым и Далмау. ^{[ 11 ]} Пусть Γ — конечный язык ограничений в булевой области. Если задача #CSP(Γ) вычислима за полиномиальное время, то Γ имеет операцию Мальцева как полиморфизм. В противном случае задача #CSP(Γ) является #P-полной . Операция Мальцева m — это тернарная операция, удовлетворяющая условию $m(x,y,y)=m(y,y,x)=x.$ Примером операции Мальцева является операция Меньшинства, данная в современной алгебраической формулировке теоремы дихотомии Шефера, приведенной выше. Таким образом, когда Γ имеет операцию меньшинства как полиморфизм, можно не только определить CSP(Γ) за полиномиальное время, но и вычислить #CSP(Γ) за полиномиальное время. Всего существует 4 операции Мальцева над булевыми переменными, определяемыми значениями $m(T,F,T)$ и $m(F,T,F)$ . Пример менее симметричного варианта дается $m(x,y,z)=(x\wedge z)\vee (\neg y\wedge (x\vee z))$ . В других областях, таких как группы , примеры операций Мальцева включают: $x-y+z$ и $xy^{-1}z.$ Для более крупных областей, даже для области размера три, существование полиморфизма Мальцева для Γ является недостаточным условием управляемости #CSP(Γ). Однако из отсутствия полиморфизма Мальцева для Γ следует #P-трудность #CSP(Γ).

См. также

Теоремы классификации Max/min CSP/Ones , аналогичный набор ограничений для задач оптимизации.

Ссылки

^ Шефер, Томас Дж. (1978). «Сложность проблем выполнимости». СТОК 1978 . стр. 216–226. дои : 10.1145/800133.804350 .
^ Перейти обратно: ^а ^б Шефер (1978, стр. 218 слева) определяет аффинную формулу как x ₁ ⊕ ... ⊕ x _n = c , где каждый x _i является переменной, c — константа, т.е. истина или ложь , и « ⊕" обозначает XOR , т.е. сложение в булевом кольце .
^ Чен, Хуби (декабрь 2009 г.). «Свидание логики, сложности и алгебры». Обзоры вычислительной техники ACM . 42 (1): 1–32. arXiv : cs/0611018 . дои : 10.1145/1592451.1592453 . S2CID 11975818 .
^ Чен, Хуби (декабрь 2006 г.). «Свидание логики, сложности и алгебры». Новости ACM SIGACT (колонка логики) . 37 (4): 85–114. arXiv : cs/0611018 . дои : 10.1145/1189056.1189076 . S2CID 14130916 .
^ Чен (2006), стр.8, предложение 3.9; Чен использует сокращение «многие-единицы» за полиномиальное время.
^ Чен (2006), стр.9, теорема 3.13.
^ Чен (2006), стр.11, теорема 3.15.
^ Аллендер, Эрик; Бауланд, Майкл; Иммерман, Нил ; Шнор, Хеннинг; Воллмер, Гериберт (июнь 2009 г.). «Сложность проблем выполнимости: уточнение теоремы Шефера» (PDF) . Журнал компьютерных и системных наук . 75 (4): 245–254. дои : 10.1016/j.jcss.2008.11.001 . Проверено 19 сентября 2013 г.
^ Бодирский, Мануэль; Пинскер, Майкл (2015). «Теорема Шефера для графов». Дж. АКМ . 62 (3): 19:1–19:52. arXiv : 1011.2894 . дои : 10.1145/2764899 . S2CID 750401 .
^ Крейну, Надя; Германн, Мики (1996). «Сложность задач подсчета обобщенных выполнимостей» . Информация и вычисления . 125 (1): 1–12. дои : 10.1006/inco.1996.0016 . ISSN 0890-5401 .
^ Булатов Андрей А.; Далмау, Виктор (1 мая 2007 г.). «К теореме дихотомии для задачи удовлетворения ограничений счета» . Информация и вычисления . 205 (5): 651–678. дои : 10.1016/j.ic.2006.09.005 . hdl : 10230/36327 . ISSN 0890-5401 .

[1] Шефер, Томас Дж. (1978). «Сложность проблем выполнимости». СТОК 1978 . стр. 216–226. дои : 10.1145/800133.804350 .

[affine-2] Перейти обратно: ^а ^б Шефер (1978, стр. 218 слева) определяет аффинную формулу как x ₁ ⊕ ... ⊕ x _n = c , где каждый x _i является переменной, c — константа, т.е. истина или ложь , и « ⊕" обозначает XOR , т.е. сложение в булевом кольце .

[3] Чен, Хуби (декабрь 2009 г.). «Свидание логики, сложности и алгебры». Обзоры вычислительной техники ACM . 42 (1): 1–32. arXiv : cs/0611018 . дои : 10.1145/1592451.1592453 . S2CID 11975818 .

[4] Чен, Хуби (декабрь 2006 г.). «Свидание логики, сложности и алгебры». Новости ACM SIGACT (колонка логики) . 37 (4): 85–114. arXiv : cs/0611018 . дои : 10.1145/1189056.1189076 . S2CID 14130916 .

[5] Чен (2006), стр.8, предложение 3.9; Чен использует сокращение «многие-единицы» за полиномиальное время.

[6] Чен (2006), стр.9, теорема 3.13.

[7] Чен (2006), стр.11, теорема 3.15.

[8] Аллендер, Эрик; Бауланд, Майкл; Иммерман, Нил ; Шнор, Хеннинг; Воллмер, Гериберт (июнь 2009 г.). «Сложность проблем выполнимости: уточнение теоремы Шефера» (PDF) . Журнал компьютерных и системных наук . 75 (4): 245–254. дои : 10.1016/j.jcss.2008.11.001 . Проверено 19 сентября 2013 г.

[9] Бодирский, Мануэль; Пинскер, Майкл (2015). «Теорема Шефера для графов». Дж. АКМ . 62 (3): 19:1–19:52. arXiv : 1011.2894 . дои : 10.1145/2764899 . S2CID 750401 .

[10] Крейну, Надя; Германн, Мики (1996). «Сложность задач подсчета обобщенных выполнимостей» . Информация и вычисления . 125 (1): 1–12. дои : 10.1006/inco.1996.0016 . ISSN 0890-5401 .

[11] Булатов Андрей А.; Далмау, Виктор (1 мая 2007 г.). «К теореме дихотомии для задачи удовлетворения ограничений счета» . Информация и вычисления . 205 (5): 651–678. дои : 10.1016/j.ic.2006.09.005 . hdl : 10230/36327 . ISSN 0890-5401 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]