De quoi se nourrissent les théorèmes de dichotomie?

10

Il est bien connu que certaines catégories de NP -Problèmes Ont dichotomie théorèmes, qui garantit que toutes les tâches de la classe est soit NP -complete ou est en P . Le résultat le plus connu est le théorème de dichotomie de Schaefer , ainsi qu'un certain nombre de généralisations.

Je crois comprendre que prouver ces théorèmes de dichotomie n'est pas vraiment facile. Je me demande s'il y a une explication relativement courte pour laquelle certaines classes ont des théorèmes de dichotomie, tandis que d'autres n'en ont pas? Quelle est la structure de problème essentielle qui rend ces théorèmes possibles? Ou peut-être qu'il n'y a pas une telle structure clairement comprise, c'est plutôt un mystère dans chaque cas pourquoi la classe a ou n'a pas un théorème de dichotomie?

cc.complexity-theory np descriptive-complexity Andras Farago
la source
2
Bonne question. Je pense qu'une intuition est que nous limitons les problèmes à une classe qui a de belles descriptions.
Kaveh
5
Ce n'est pas une réponse, mais indique peut-être où une réponse pourrait (ne pas) être: si la classe de problèmes est assez grande pour inclure tout (ou même juste un sous-ensemble particulier), alors le théorème de Ladner s'appliquera et il n'y aura pas de dichotomie. Donc, une classe avec dichotomie doit au moins être suffisamment structurée pour éviter Ladner ...NP
Joshua Grochow
1
Les dichotomies se produisent lorsque le langage est trop grossier pour faire de fines distinctions.
András Salamon

Réponses:

2

Pour le cas du théorème de dichotomie de Schaefer, de manière informelle, le pouvoir expressif universel des formules CNF booléennes construites à partir de relations logiques non Schaefer est à l'origine de la dichotomie. Chaque relation logique peut être définie par une telle formule en utilisant un quantificateur existentiel. Ceci est formellement énoncé dans le théorème d'expressibilité de Schaefer (Théorème 2.5).

Mohammad Al-Turkistany
la source