É 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?
cc.complexity-theory
np
descriptive-complexity
Andras Farago
fonte
fonte
Respostas:
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).
fonte