Por que os Teoremas de Shaefer e Mahaney não implicam P = NP?

14

Tenho certeza de que alguém já pensou nisso antes ou imediatamente o descartou, mas por que a teoria da dicotomia de Schaefer, juntamente com o teorema de Mahaney sobre conjuntos esparsos, não implica P = NP?

Aqui está o meu raciocínio: Crie um idioma que seja igual a SAT cruzado por um conjunto esparso infinito e decidível. Então também deve ser escasso. Como não é trivial, afim, 2-sat ou Horn-sat, pelo teorema de Shaefer, ele deve ser NP-completo. Mas então temos um conjunto NP completo esparso, de acordo com o teorema de Mahaney, P = NP.eueueu

Onde estou errado aqui? Suspeito que estou entendendo mal ou aplicando mal o teorema de Shaefer, mas não vejo o porquê.

Ari
fonte
1
Intimamente relacionados: cs.stackexchange.com/q/42544/755 (leia as respostas antes de tentar entender todos os detalhes da questão, as respostas são relativamente auto-suficiente)
DW
já me perguntei sobre isso antes de pedir tanto! o truque é que schaefers thm não está realmente afirmando que não há idiomas intermediários "entre" P / NP, é mais sutil. Além disso, tente estudar a classe NPI, também conhecida como NP intermediária, existem muitas referências em Teoria da Computação . muitos problemas importantes estão "no" NPI, os dois principais / famosos são fatoração e isomorfismo gráfico.
vzn
em resumo Shaefer thm soa como um thm sobre o SAT, mas na verdade é sobre uma linguagem estreita relacionada ao SAT que aparentemente não é nem NP difícil nem NP completo ....? têm sido à procura de um "livro de graduação" apresentação nível de Shaefer thm ....
vzn

Respostas:

13

SUMAT(S)CSP(Γ)eu

Yuval Filmus
fonte
impressionante, mas o que exatamente é SAT (S)? plz carne isto mais (embora reconhecidamente / claramente alguns outros pensam que é necessário!)
vzn
Isso é explicado com muita clareza na página da Wikipedia sobre o teorema de Schaefer, da qual copiei essa notação.
Yuval Filmus
1
mas mesmo assim ainda acho que tudo isso poderia ser explicado melhor. "Schaefer define um problema de decisão que ele chama de problema de satisfação generalizada". mas aparentemente não é tão generalizado então ....? por exemplo, por que o idioma que ele estuda é importante e não artificial? é usado em outro lugar no CS que não seja o seu artigo? quais são as implicações mais amplas desse teorema, existe alguma ou é uma curiosidade isolada que parece não levar a lugar algum? poderia de alguma forma ser usado em um ataque P vs NP ou não? etc
vzn 22/06/2015