Теорема шеферса о дихотомии - Schaefers dichotomy theorem

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

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

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

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

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

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

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

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

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

Это современное понимание использует алгебру, в частности, универсальная алгебра. Для теоремы Шефера о дихотомии наиболее важным понятием универсальной алгебры является понятие полиморфизма. Операция ${\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. постоянная унарная операция 0;
2. постоянная унарная операция 1;
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 (Γ).

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

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

Обобщения

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

Теорема Шефера о дихотомии недавно была обобщена на более широкий класс отношений.^[9]

Связанных с работой

Если задача состоит в том, чтобы подсчитать количество решений, которое обозначается как #CSP (Γ), то имеет место аналогичный результат Крейну и Германа.^[10] Пусть Γ - конечный язык ограничений над булевой областью. Задача #CSP (Γ) вычислима за полиномиальное время, если Γ имеет операцию Мальцева как полиморфизм. В противном случае задача #CSP (Γ) будет # P-complete. Мальцевская операция м - тернарная операция, удовлетворяющая ${\displaystyle m(x,y,y)=m(y,y,x)=x.}$ Примером операции Мальцева является операция меньшинства, данная в современной алгебраической формулировке теоремы о дихотомии Шефера выше. Таким образом, когда Γ имеет операцию меньшинства как полиморфизм, можно не только решить CSP (Γ) за полиномиальное время, но и вычислить #CSP (Γ) за полиномиальное время. Всего имеется 4 операции Мальцева над булевыми переменными, определяемыми значениями ${\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.}$

Для более крупных областей, даже для области размера три, наличие мальцевского полиморфизма для Γ больше не является достаточным условием для управляемости #CSP (Γ). Однако отсутствие полиморфизма Мальцева для Γ по-прежнему означает # P-твердость #CSP (Γ).

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

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

Рекомендации

1. Шефер, Томас Дж. (1978). «Сложность проблем выполнимости». STOC 1978. С. 216–226. Дои:10.1145/800133.804350.
2. Шефер (1978, с. 218 слева) определяет аффинная формула иметь форму Икс₁ ⊕ ... ⊕ Икс_п = c, где каждый Икс_я переменная, c является константой, т.е. истинный или же ложный, а "⊕" означает XOR, т.е. сложение в Логическое кольцо.
3. Чен, Хуби (декабрь 2009 г.). «Встреча логики, сложности и алгебры». Опросы ACM Computing. 42 (1): 1–32. arXiv:cs / 0611018. Дои:10.1145/1592451.1592453.
4. Чен, Хуби (декабрь 2006 г.). «Встреча логики, сложности и алгебры». Новости SIGACT (логическая колонка). arXiv:cs / 0611018.
5. Chen (2006), стр. 8, предложение 3.9; Чен использует полиномиальное время много-одно сокращение
6. Chen (2006), стр.9, теорема 3.13
7. Chen (2006), стр.11, теорема 3.15
8. Аллендер, Эрик; Бауланд, Майкл; Иммерман, Нил; Шнор, Хеннинг; Фоллмер, Хериберт (июнь 2009 г.). «Сложность проблем выполнимости: уточнение теоремы Шефера» (PDF). Журнал компьютерных и системных наук. 75 (4): 245–254. Дои:10.1016 / j.jcss.2008.11.001. Получено 2013-09-19.
9. Бодирский, Мануэль; Пинскер, Майкл (2015). «Теорема Шефера для графов». J. ACM. 62 (3): 19:1–19:52. arXiv:1011.2894. Дои:10.1145/2764899.
10. Крейну, Надя; Германн, Мики (1996). «Сложность задач подсчета обобщенной выполнимости». Информация и вычисления. 125 (1): 1–12. Дои:10.1006 / inco.1996.0016. ISSN  0890-5401.