Teorema de Ladner vs. Teorema de Schaefer

27

Ao ler o artigo "É hora de declarar vitória na contagem da complexidade?" no blog "Godel's Lost Letter and P = NP" , eles mencionaram a dicotomia para CSP's. Depois de algum link a seguir, pesquisando e pesquisando, encontrei o Teorema de Ladner :

Teorema de Ladner: Se , então existem problemas em que não são completos.N PPPNPNPPNP

e ao teorema de Schaefer :

Teorema da dicotomia de Schaefer: para cada idioma de restrição acima de , se for Schaefer, é passível de solução polinomial. Caso contrário, é completo.{ 0 , 1 } Γ C S P ( Γ ) C Γ{0,1} ΓCSP(Γ)N PCSP(Γ)NP

Eu li isto para dizer que, por Ladner de, há problemas que não são nem nem -completo, mas por Schaefer de, problemas ou são e -completo só.N PPNPN PPNP

o que estou perdendo? Por que esses dois resultados não se contradizem?

Peguei a versão condensada das declarações do teorema acima daqui . Na seção "Comentários finais", ele diz "Assim, se um problema estiver em mas não estiver , ele não poderá ser formulado como CSP" .N PNPPNP

Isso significa que os problemas do perdem algumas instâncias do ? Como isso é possível?N PSATNP

user834
fonte
2
Não há um pequeno problema em que é preciso ter cuidado ao definir "linguagem de restrição" e "problema"? O teorema de Schaefers (tanto quanto me lembro), considera apenas as linguagens dadas tomando o fechamento sob conjunção e substituição variável de algum conjunto S de relações. No entanto, pode-se construir conjuntos de problemas de restrições que não são cobertos por isso e, portanto, podem ser tratáveis, mas não Schaefer. Presumivelmente, o conjunto de problemas que Ladner constrói simplesmente não é definível em termos do fechamento sob conjunção e substituição variável de um conjunto de relações.
precisa saber é o seguinte
1
Eu acho que você deve alterar a última frase, uma vez que uma instância não possui complexidade (não trivial), conjuntos de instâncias têm complexidade. Isso significa que nenhum conjunto NPI de instâncias é expressável como . C S P ( Γ )SATCSP(Γ)
Kaveh

Respostas:

15

Como afirma Massimo Lauria, os problemas da forma CSP ( ) são bastante especiais. Portanto, não há contradição.Γ

Qualquer ocorrência do problema satisfação restrição pode ser representado como um par de estruturas relacionais S e T , e um tem de decidir se existe um homomorphism estrutura relacional da fonte de S para o alvo t . (S,T)STST

CSP ( ) é um tipo especial de problema de satisfação de restrições. Consiste em todos os pares de estruturas relacionais que são construídas usando apenas as relações de Γ na estrutura relacional de destino: CSP ( Γ ) = { ( S , T ) todas as relações de  T  são de  Γ } . O Teorema de Schaefer diz que quando Γ contém apenas relações acima de { 0 , 1 } , então CSP ( ΓΓΓΓ{(S,T)all relations of T are from Γ}Γ{0,1}Γ) está completo em NP ou em P, mas não diz nada sobre outras coleções de instâncias de CSP.

Como um exemplo extremo, pode-se começar com algum CSP ( ) que esteja completo com NP e "furos" no idioma. (Ladner fez isso com SAT na prova de seu teorema.) O resultado é um subconjunto que contém apenas algumas das instâncias e não mais na forma CSP ( Γ ' ) para qualquer Γ ' . Repetir a construção produz uma hierarquia infinita de linguagens de dureza decrescente, assumindo P ≠ NP.ΓΓΓ

András Salamon
fonte
23

Você precisa entender que os problemas de têm uma estrutura que os problemas genéricos de S A T não possuem. Vou dar um exemplo simples. Seja Γ = { { ( 0 , 0 ) , ( 1 , 1 ) } , { ( 0 , 1 ) , ( 1 , 0 ) } }CSPSATΓ={{(0,0),(1,1)},{(0,1),(1,0)}}. Essa linguagem é tal que você só pode expressar igualdade e desigualdade entre duas variáveis. Claramente, qualquer conjunto de restrições é passível de solução em tempo polinomial.

Vou apresentar dois argumentos para esclarecer a relação entre e cláusulas. Note-se que tudo o que se segue assume PN P .CSPPNP

Primeiro : as restrições têm um número fixo de variáveis, enquanto a codificação de problemas intermediários pode precisar de grandes cláusulas. Isso não é necessariamente um problema quando tais restrições grandes podem ser expressas como uma conjunção de pequenas usando variáveis ​​auxiliares. Infelizmente, esse nem sempre é o caso do general .Γ

Suponha apenas para conter o O R de cinco variáveis. É claro que você pode expressar a O R de menos variáveis, repetindo entradas. Você não pode expressar uma maior ó R pois a maneira de fazê-lo usando variáveis de extensão requer disjunções de literais positivos e negativos. Γ representa relações em variáveis , e não em literais . Na verdade, quando você pensa sobre 3 S A T como um C S P você precisa y para conter quatro relações de disjunção com algumas entradas negadas (de zero a três).ΓORORORΓSATCSPΓ

Segundo : cada relação em pode ser expressa como um lote de cláusulas com (digamos) três literais. Cada restrição deve ser um lote inteiro dessas cláusulas. No exemplo com constrangimentos igualdade / desigualdade não se pode ter um binário Um N D (isto é, relação ( 1 , 1 ) ) sem aplicação de um binário negada O R (isto é, relação ( 0 , 0 ) ) nas mesmas variáveis.ΓAND(1,1)OR(0,0)

Espero que isso ilustre para você que instâncias obtidas de C S P s possuem uma estrutura muito peculiar, imposta pela natureza de Γ . Se a estrutura estiver muito apertada, você não poderá expressar problemas difíceis. SATCSPΓ

Um corolário do Teorema de Schaefer é que, sempre que impõe uma estrutura frouxa o suficiente para expressar problemas de decisão de N P P , o mesmo Γ permite liberdade suficiente para expressar instâncias 3- S A T gerais .ΓNPPΓSAT

MassimoLauria
fonte
1
Acrescentar à excelente resposta de MassimoLauria; Não há contradição. Dê uma olhada neste artigo da Wikipedia, que possui uma seção que explica, em palavras simples, a relação entre o Teorema de Ladner e o Teorema de Schaefer.
Mohammad Al-Turkistany
Só para ter certeza de que entendi, você está dizendo que a versão restrita de 'S no teorema de Schaefer não é capaz de codificar uma instância arbitrária de 3 S A T ou que as instâncias de C S P ( Γ ) podem crescer super-polinomialmente para alguma classe de problemas 3- S A T ? CSPSATCSP(Γ)SAT
user834
No Teorema de Schaefer, vários tipos de são mostrados para induzir algoritmos de tempo polinomial. Eu acho (mas não tenho certeza) que alguns deles não podem expressar um 3- S A T genérico . No entanto, considere Γ o conjunto de "cláusulas de trompa 3". Estes são decidíveis em polítime e qualquer cálculo determinístico no tempo t pode ser codificado como uma fórmula H o r n - S A T de tamanho p o l y ( t ) . Portanto, acho que você pode codificar cálculos exponencialmente longos com um C S P exponencialmente longoΓSATΓtHornSATpoly(t)CSP(ou seja, exponencialmente muitas variáveis). Isso faz sentido?
MassimoLauria
Eu acho que a maneira correta de dizer isso é que os CSPs na estrutura de Schaefer não podem codificar um problema arbitrário de NP (o 3-SAT é de fato um problema canônico de CSP). Observe que esta é uma declaração condicional (a menos que P = NP).
Chandra Chekuri
@ChandraChekuri, desculpe-me por ser tão densa, mas você está dizendo que os CSPs na estrutura de Schaefer não podem codificar instâncias arbitrárias do 3-SAT? O CSP pode, em geral, codificar 3-SAT, mas a versão restrita dos CSPs na estrutura de Schaefer não pode?
precisa saber é o seguinte