Toward a complexity classification of CSP through kernel width.

Accueil || Parcours || Recherche || S'enregistrer || Mon Compte || Contacts || Aide || Langues

Richoux, Florian (2009) Toward a complexity classification of CSP through kernel width. Doctorat Informatique, Laboratoire d'Informatique de l'École Polytechnique, EP/X p.88.

Plein texte disponible en tant que : - memoire_submitted.pdf ( 635 Kb )

Licence: Copyright

Résumé

Constraint Satisfaction Problems (CSP) constitute a universal formalism allowing to modelize a huge number of algorithmical and combinatorial problems, such as problems over graphs, databases, artificial intelligence, …

This thesis is in line with the study of the computational complexity of CSP. It is a very active research domain for which there exists dedicated sessions in some highest conferences in algorithmic, logic and artificial intelligennce such as IJCAI and AAAI.

The starting point of this thesis was to study some restrictions of CSP and to fully characterize the computational complexity of these sub-problems. This goal has been reached with the complete characterization of monotone CSP over finite domains of an arbitrary cardinality and over infinite countable domains. These results lead to two international and one national publications. This thesis also describes a complete characterization of homogeneous co-Boolean CSP and gives a first approach of a complete characterization for general co-Boolean CSP. Most of all, this thesis develops a new method based on the kernel width which seems to be very promissing to characterize the computational complexity of the general CSP problem, and starts to give some firsts innovating results on the complexity.

Statistiques de consultation

Administrateurs de l'archive uniquement : éditer cet enregistrement