Sur la complexité algorithmique des problèmes de satisfaction de contraintes disjonctifs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

Sur la complexité algorithmique des problèmes de satisfaction de contraintes disjonctifs

Résumé

Les problèmes de satisfaction de contraintes (CSP) constituent une puissante manière de capturer de nombreux problèmes combinatoires. Le CSP général est connu pour être NP-complet, mais la complexité du problème paramétré CSP(S) dépend uniquement de son paramètre, habituellement un ensemble de relations sur lesquelles les contraintes sont construites. Suivant ce paramètre, il existe des instances de CSP “faciles” et “difficiles”. Dans cet article, nous montrons un théorème dichotomique pour tous domaines finis de CSP où la disjonction entre contraintes est autorisée. Cette dichotomie est basée sur un critère simple, nous permettant de classer les CSP disjonctifs comme étant dans P ou étant NP-complet. Nous prouvons également que le méta-problème, à savoir vérifier le critère de dichotomie pour les problèmes de satisfaction de contraintes disjonctifs, est fixed-parameter tractable. De plus, nous présentons un algorithme en temps polynomial répondant à cette question pour les CSP disjonctifs sur un domaine ternaire.
Fichier principal
Vignette du fichier
pages-209-218-article6.pdf (294 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00291615 , version 1 (27-06-2008)

Identifiants

  • HAL Id : inria-00291615 , version 1

Citer

Miki Hermann, Florian Richoux. Sur la complexité algorithmique des problèmes de satisfaction de contraintes disjonctifs. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, LINA - Université de Nantes - Ecole des Mines de Nantes, Jun 2008, Nantes, France. pp.209-218. ⟨inria-00291615⟩
104 Consultations
56 Téléchargements

Partager

Gmail Facebook X LinkedIn More