Теорема Ладнера против теоремы Шефера

Читая статью «Пора ли объявить победу в подсчете сложностей?» в блоге «Потерянное письмо Годеля и P = NP» они упомянули дихотомию для CSP. После некоторой ссылки, поиска в Google и википедирования, я наткнулся на теорему Ладнера :

Теорема Ладнера: если , то в существуют проблемы , которые не являются -полными. ${\bf P} \ne {\bf NP}$ ${\bf NP} \setminus {\bf P}$ ${\bf NP}$

и к теореме Шефера :

Теорема Шихера о дихотомии. Для любого языка ограничений над , если является шеферовым, то разрешимо за полиномиальное время. В противном случае является -полным. $\ \Gamma$ $\{0, 1\}$ $\ \Gamma$ ${\bf CSP}(\Gamma)$ ${\bf CSP}(\Gamma)$ ${\bf NP}$

Я прочитал это, чтобы означать, что у Ладнера есть проблемы, которые не являются ни ни полными, но, по мнению Шефера, проблемы являются только и полными. ${\bf P}$ ${\bf NP}$ ${\bf P}$ ${\bf NP}$

Чего мне не хватает? Почему эти два результата не противоречат друг другу?

Я взял сокращенную версию приведенных выше утверждений теоремы отсюда . В своем разделе «Заключительные комментарии» он говорит: «Таким образом, если проблема в но она не является неполной, ее нельзя сформулировать как CSP». ${\bf NP} \setminus {\bf P}$ ${\bf NP}$

Означает ли это, что проблемы пропускаются в некоторых случаях в ? Как это возможно? ${\bf SAT}$ ${\bf NP}$

cc.complexity-theory np-hardness complexity-classes sat csp user834
источник

Есть ли небольшая проблема в том, что нужно быть осторожным при определении «языка ограничений» и «проблемы»? Теорема Шеферса (насколько я помню) рассматривает только языки, заданные путем взятия замыкания при конъюнкции и подстановки переменных некоторого множества S отношений. Тем не менее, можно построить набор задач с ограничениями, которые не охватываются этим, и поэтому могут быть отслеживаемыми, но не по Шеферу. Предположительно, набор проблем, которые конструирует Ладнер, просто не определим с точки зрения замыкания при конъюнкции и переменной подстановки множества отношений.

MGwynne

S A T

$\mathsf{SAT}$

C S P (Γ)

$\mathsf{CSP}(\Gamma)$

Ответы:

$\Gamma$

$(S,T)$ $S$ $T$ $S$ $T$

$\Gamma$ $\Gamma$ $\Gamma$ $\{(S,T) \mid \text{all relations of } T \text{ are from } \Gamma\}$ $\Gamma$ $\{0,1\}$ $\Gamma$ ) либо NP-полная, либо в P, но ничего не говорит о других коллекциях экземпляров CSP.

$\Gamma$ $\Gamma'$ $\Gamma'$

Андраш Саламон
источник

$\mathsf{CSP}$ $\mathbf{SAT}$ $\Gamma=\{\{(0,0),(1,1)\},\{(0,1),(1,0)\}\}$ , Этот язык таков, что вы можете выражать только равенство и неравенство между двумя переменными. Ясно, что любой такой набор ограничений разрешим за полиномиальное время.

$\mathsf{CSP}$ $\mathbf{P}\not=\mathbf{NP}$

$\Gamma$

$\Gamma$ $\mathsf{OR}$ $\mathsf{OR}$ $\mathsf{OR}$ $\Gamma$ $\mathbf{SAT}$ $\mathsf{CSP}$ $\Gamma$

$\Gamma$ $\mathsf{AND}$ ${(1,1)}$ $\mathsf{OR}$ ${(0,0)}$

$\mathbf{SAT}$ $\mathsf{CSP}$ $\Gamma$

$\Gamma$ $\mathbf{NP\backslash P}$ $\Gamma$ $\mathsf{SAT}$

MassimoLauria
источник

Чтобы добавить к отличному ответу МассимоЛориа; Здесь нет противоречия. Взгляните на эту статью в Википедии, в которой есть раздел, который объясняет, простыми словами, связь между теоремой Ладнера и теоремой Шефера.

Мухаммед Аль-Туркистани

C S P

${\bf CSP}$

S A T

${\bf SAT}$

C S P (Γ)

${\bf CSP}(\Gamma)$

S A T

${\bf SAT}$

Γ

$\Gamma$

S A T

$\mathbf{SAT}$

Γ

$\Gamma$

t

$t$

H o r n

$\mathsf{Horn}$

S A T

$\mathbf{SAT}$

p o l y (t)

$poly(t)$

C S P

$\mathsf{CSP}$ (т.е. экспоненциально много переменных). Имеет ли это смысл?

MassimoLauria

Я думаю, что правильный способ сказать, что CSP в структуре Шефера не может кодировать произвольную проблему NP (3-SAT на самом деле является канонической проблемой CSP). Обратите внимание, что это условный оператор (если P = NP).

Чандра Чекури

@ChandraChekuri, извините, пожалуйста, за то, что я такой дремучий, но вы говорите, что CSP в среде Шефера не может кодировать произвольные экземпляры 3-SAT? CSP может, в общем, кодировать 3-SAT, но ограниченная версия CSP в структуре Шефера не может?

user834