Answer set programming

L’answer set programming (ASP) est une forme de programmation déclarative adaptée aux problèmes de recherche combinatoires (par exemple, sudoku et coloration de graphes). Dans le contexte de la programmation logique, cette approche distingue deux types de négation — la négation par manque d'information, dite négation par défaut, et la négation forte ou négation logique. La négation par défaut permet de raisonner en l'absence d'information et rend l'ASP non monotone. L'exemple suivant, illustre le fonctionnement de la négation par défaut: Si « X est un oiseau » mais pas « X est une autruche » alors « X vole » « Titi est un oiseau » On peut déduire de ce programme le fait « Titi vole ». En effet, ici nous n'avons aucune information qui nous indique que Titi est une autruche. Cependant, si nous avions les informations «Lola est un oiseau et une autruche », alors nous ne pouvons pas déduire que Lola vole. La négation forte quant à elle demande une preuve qu'un fait est faux. Dans cet exemple, il faudrait donc prouver que Titi n'est pas une autruche pour en déduire qu'il vole. En ASP, la résolution de problème se réduit à calculer des modèles stables, c'est-à-dire où la négation par défaut produit des modèles logiquement consistants. Dans un sens plus général, ASP inclut des techniques de représentation des connaissances et l’évaluation de requêtes dans le style Prolog, pour résoudre les problèmes qui se posent dans ces applications. ASP permet de décider les problèmes dans NP et plus généralement les problèmes de la classe NPNP (voir hiérarchie polynomiale, l'existence d'un modèle stable est NPNP-complet).