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 P ∖ P
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 ( Γ ) CN P
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 PN P
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 P
Isso significa que os problemas do perdem algumas instâncias do ? Como isso é possível?N P
Respostas:
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) S T S T
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) ∣ todas as relações de T são de Γ } Γ { 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.Γ Γ′ Γ′
fonte
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 ) } }CSP SAT Γ={{(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 P ≠ N P .CSP P≠NP
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).Γ OR OR OR Γ SAT CSP Γ
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.SAT CSP Γ
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 .Γ NP∖P Γ SAT
fonte