J'ai suivi un cours une fois sur la calculabilité et la logique. Le matériel comprenait une corrélation entre les classes de complexité / calculabilité (R, RE, co-RE, P, NP, Logspace, ...) et la logique (Calcul de prédicats, logique du premier ordre, ...).
La corrélation comprenait plusieurs résultats dans un domaine, obtenus à l'aide de techniques de l'autre domaine. On a supposé que P! = NP pourrait être attaqué en tant que problème dans Logic (en projetant le problème du domaine des classes de complexité vers la logique).
Existe-t-il un bon résumé de ces techniques et résultats?
cc.complexity-theory
lo.logic
computability
ripper234
la source
la source
Neil Immerman a produit un beau diagramme qui fournit en un coup d'œil des correspondances entre les classes de complexité et les logiques interprétées par des modèles finis. C'est sur la couverture de son livre, et aussi au bas de sa page Web ici: http://www.cs.umass.edu/~immerman/
la source
Je connais deux façons d'associer la logique aux classes de complexité. Le premier est la complexité descriptive qui est la théorie des modèles mentionnée dans d’autres réponses. (Revenons à la caractérisation de par Ronald Fagin .)NP
Antonina Kolokolova a travaillé sur les relations entre ces deux approches.
la source
Pour ceux qui ne connaissent pas la multitude d'acronymes trouvés dans le grand diagramme d'Immerman, il existe un article de Wikipedia sur la complexité descriptive . Il devrait y avoir un diagramme avec des liens afin que vous puissiez directement rechercher la définition dans Complexity Zoo et d’autres sources. J'aimerais aussi mieux voir les relations avec les langages formels / grammaires correspondants et où vous pouvez trouver la preuve.
Ce n'est pas une réponse, mais un commentaire à la réponse d'Aarons, que je ne peux commenter pour une raison quelconque.
la source