Em que se alimentam os teoremas da dicotomia?

10

É bem conhecido que certas classes de NP -Problemas Tem dicotomia teoremas, que garantia de que todas as tarefas na classe ou é NP -completo ou está em P . O resultado mais conhecido é o teorema da dicotomia de Schaefer , juntamente com várias generalizações.

Entendo que provar esses teoremas da dicotomia não é realmente fácil. Gostaria de saber se existe alguma explicação relativamente curta para o motivo de certas classes terem teoremas de dicotomia, enquanto outras não. Qual é a estrutura essencial de problemas que possibilita esses teoremas? Ou talvez não exista uma estrutura tão claramente entendida, mas é um mistério em cada caso por que a classe possui ou não um teorema da dicotomia?

Andras Farago
fonte
2
Boa pergunta. Penso que uma intuição é que estamos restringindo os problemas a uma classe que tem boas descrições.
Kaveh #
5
Isso não é uma resposta, mas talvez aponte para onde uma resposta pode (não) estar: se a classe de problemas for grande o suficiente para incluir todos os (ou mesmo apenas um subconjunto específico dela), então o de Ladner Teorema será aplicado e não haverá dicotomia. Assim, uma classe com dicotomia, pelo menos, tem que ser estruturado o suficiente para evitar Ladner ...NP
Joshua Grochow
11
As dicotomias ocorrem quando a linguagem é muito grossa para fazer distinções finas.
András Salamon

Respostas:

2

Para o caso do teorema da dicotomia de Schaefer, informalmente, o poder expressivo universal das fórmulas booleanas da CNF construídas a partir de relações lógicas não-Schaefer está por trás da dicotomia. Toda relação lógica é definível por essa fórmula usando o quantificador existencial. Isto é afirmado formalmente no teorema da expressibilidade de Schaefer (Teorema 2.5).

Mohammad Al-Turkistany
fonte