La résolution étendue étroite

Résumé : La résolution étendue (ER) (c'est-à-dire, la résolution incorporant la règle d'extension) est un système de preuve plus puissant que la résolution standard (Res) car elle permet de résoudre en temps polynômial certaines classes d'instances que Res ne peut traiter qu'en temps exponentiel. Cependant, elle est très difficile à mettre en pratique car la règle d'extension accroit considérablement la taille de l'espace de recherche de la preuve. On dit qu'une résolution est étroite si l'application de la règle de résolution produit une résolvante contenant au maximum trois littéraux. Dans cet article nous présentons deux variantes de ER : la résolution étendue étroite (ER3) et la résolution à refragmentation. Ces deux systèmes de preuves p-simulent ER : toute preuve de l'une n'est que polynômialement plus longue que celle de l'autre. ER3 consiste simplement à n'autoriser que des résolutions étroites dans ER. Ceci permet une diminution exponentielle de l'espace de recherche d'une preuve dans ER. La résolution à refragmentation est une variante de ER3 qui permet une intégration facile de la résolution étendue dans n'importe quel solveur appliquant la résolution.
Type de document :
Communication dans un congrès
JFPC'12 - 12e Journées Francophones de Programmation par Contraintes, May 2012, Toulouse, France. 2012
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00818180
Contributeur : Nicolas Prcovic <>
Soumis le : vendredi 26 avril 2013 - 11:22:44
Dernière modification le : mercredi 12 septembre 2018 - 01:27:34
Document(s) archivé(s) le : lundi 3 avril 2017 - 23:49:03

Fichier

jfpc12.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00818180, version 1

Collections

Citation

Nicolas Prcovic. La résolution étendue étroite. JFPC'12 - 12e Journées Francophones de Programmation par Contraintes, May 2012, Toulouse, France. 2012. 〈hal-00818180〉

Partager

Métriques

Consultations de la notice

112

Téléchargements de fichiers

111