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

Когда конечный набор S отношений приводит к решению задач с полиномиальным временем или NP-полных задач

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

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

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

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

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

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

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

Современная подача

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

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

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

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

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

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

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

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

Отношение R называется примитивно позитивно определимым , или коротко pp-определимым , из множества Γ отношений, если R ( v ₁ , ... , v _k ) ⇔ ∃ x ₁ ... x _m . 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 ( x , y , z ) ⇔ ∃ a . 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 — это тернарная операция, которая удовлетворяет Примером операции Мальцева является операция Minority, приведенная в современной алгебраической формулировке теоремы Шефера о дихотомии выше. Таким образом, когда Γ имеет операцию Minority как полиморфизм, можно не только решить CSP(Γ) за полиномиальное время, но и вычислить #CSP(Γ) за полиномиальное время. Всего существует 4 операции Мальцева над булевыми переменными, определяемые значениями и . Примером менее симметричного является . В других областях, таких как группы , примеры операций Мальцева включают и Для больших областей, даже для области размера три, существование полиморфизма Мальцева для Γ является недостаточным условием для управляемости #CSP(Γ). Однако отсутствие полиморфизма Мальцева для Γ подразумевает #P-трудность #CSP(Γ). ${\displaystyle m(x,y,y)=m(y,y,x)=x.}$ ${\displaystyle m(T,F,T)}$ ${\displaystyle m(F,T,F)}$ ${\displaystyle m(x,y,z)=(x\wedge z)\vee (\neg y\wedge (x\vee z))}$ ${\displaystyle x-y+z}$ ${\displaystyle xy^{-1}z.}$

Смотрите также

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

Ссылки

1. Шефер, Томас Дж. (1978). «Сложность проблем выполнимости». Труды десятого ежегодного симпозиума ACM по теории вычислений — STOC '78 . С. 216–226. doi :10.1145/800133.804350.
2. Шефер (1978, стр. 218 слева) определяет аффинную формулу как имеющую вид x ₁ ⊕ ... ⊕ x _n = c , где каждый x _i является переменной, c является константой, т. е. true или false , а «⊕» обозначает XOR , т. е. сложение в булевом кольце .
3. Чен, Хуби (декабрь 2009 г.). «Встреча логики, сложности и алгебры». ACM Computing Surveys . 42 (1): 1–32. arXiv : cs/0611018 . doi :10.1145/1592451.1592453. S2CID  11975818.
4. Чен, Хуби (декабрь 2006 г.). «Встреча логики, сложности и алгебры». ACM SIGACT News . 37 (4): 85–114. arXiv : cs/0611018 . doi : 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. doi : 10.1016/j.jcss.2008.11.001 . Получено 19 сентября 2013 г.
9. Бодирский, Мануэль; Пинскер, Майкл (2015). «Теорема Шефера для графов». J. ACM . 62 (3): 19:1–19:52. arXiv : 1011.2894 . doi :10.1145/2764899. S2CID  750401.
10. Creignou, Nadia; Hermann, Miki (1996). «Сложность проблем подсчета обобщенной выполнимости». Информация и вычисления . 125 (1): 1–12. doi : 10.1006/inco.1996.0016 . ISSN  0890-5401.
11. Булатов, Андрей А.; Далмау, Виктор (1 мая 2007 г.). «К теореме о дихотомии для проблемы удовлетворения ограничений подсчета». Информация и вычисления . 205 (5): 651–678. doi : 10.1016/j.ic.2006.09.005. hdl : 10230/36327 . ISSN  0890-5401.