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

27

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

Теорема Ладнера: если , то в N PP существуют проблемы , которые не являются N P -полными.PNPNPPNP

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

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

Я прочитал это, чтобы означать, что у Ладнера есть проблемы, которые не являются ни ни N P- полными, но, по мнению Шефера, проблемы являются только P и N P- полными.PNPPNP

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

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

Означает ли это, что проблемы пропускаются в некоторых случаях в N P ? Как это возможно?SATNP

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

Ответы:

15

Γ

(S,T)STST

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

ΓΓΓ

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

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

CSPPNP

Γ

ΓORORORΓSATCSPΓ

ΓAND(1,1)OR(0,0)

SATCSPΓ

ΓNPPΓSAT

MassimoLauria
источник
1
Чтобы добавить к отличному ответу МассимоЛориа; Здесь нет противоречия. Взгляните на эту статью в Википедии, в которой есть раздел, который объясняет, простыми словами, связь между теоремой Ладнера и теоремой Шефера.
Мухаммед Аль-Туркистани
CSPSATCSP(Γ)SAT
ΓSATΓtHornSATpoly(t)CSP(т.е. экспоненциально много переменных). Имеет ли это смысл?
MassimoLauria
Я думаю, что правильный способ сказать, что CSP в структуре Шефера не может кодировать произвольную проблему NP (3-SAT на самом деле является канонической проблемой CSP). Обратите внимание, что это условный оператор (если P = NP).
Чандра Чекури
@ChandraChekuri, извините, пожалуйста, за то, что я такой дремучий, но вы говорите, что CSP в среде Шефера не может кодировать произвольные экземпляры 3-SAT? CSP может, в общем, кодировать 3-SAT, но ограниченная версия CSP в структуре Шефера не может?
user834