Sur les problèmes de complexité en déduction automatique : base de Hilbert, modèles uniques et minimaux - Université de Lorraine Accéder directement au contenu
Thèse Année : 1999

Sur les problèmes de complexité en déduction automatique : base de Hilbert, modèles uniques et minimaux

Résumé

In this thesis we are interested in the complexity of sorne problems in the framework of automated deduction. We study the computational complexity of counting the Hilbert basis of a homogeneous system of linear diophantine equations. The Hilbert basis of a homogeneous system of linear Diophantine equations over non-negative integers is the set of aIl non-zero vectors that are minimal solutions. We establish lower and upper bounds for the complexity of this problem, by showing that counting the Hilbert basis is #P-hard and belongs to the class #NP. Moreover, we investigate the complexity of variants obtained by restricting the number of occurrences of the variables in the system. We also study the problem of recognizing the Hilbert basis. We analyze the problem of the Hilbert basis where the coefficients are given in unary notation. We prove that deciding whether a given solution belongs to the Hilbert basis of a given system is a coNP-complete problem in the strong sense. Furthermore, we show that given a linear Diophantine system and a set of solutions, as king whether this set represents the Hilbert basis of the system is polynomialy equivalent to the problem of deciding whether a glven set of vectors constitutes the Hilbert basis of an unknown linear Diophantine system. We also study the unique satisfiability problem that consists of deciding if there exists a unique solution to a given propositional formula. We give a dichotomy theorem for this problem by partitioning the instances of the problem between the polynomial-time solvable and coNP-hard cases.
Dans cette thèse, nous nous sommes intéressés à la complexité de certains problèmes dans le cadre de la déduction automatique. Nous étudions la complexité de comptage de la base de Hilbert d'un système d'équations diophantiennes linéaires homogène. La base de Hilbert d'un système d'équations diophantiennes linéaires homogène est l'ensemble de ses solutions entières minimales à coefficients positifs. Nous donnons une borne inférieure et une borne supérieure pour la complexité de ce problème en montrant que le comptage de la base de Hilbert est #P-difficile et appartient à la classe #NP. De plus, nous étudions la complexité de certaines variantes de ce problème quand le nombre d'occurrences de chaque variable est restreint dans le système. Nous étudions également le problème de la reconnaissance de la base de Hilbert. Nous étudions le problème de la base de Hilbert où les coefficients sont donnés en notation unaire. Nous prouvons que le problème de la minimalité d'une solution pour un système d'équations diophantiennes linéaires homogène est un problème coNP-complet au sens fort. De plus, nous montrons qu'étant donné un ensemble de vecteurs, le problème de savoir si cet ensemble représente la base de Hilbert d'un système donné en entrée est polynomialement équivalent au problème de savoir si cet ensemble représente la base de Hilbert d'un système quelconque. Nous nous sommes également intéressés au problème de l'unicité d'un modèle pour un formule propositionnelle. Nous donnons un théorème dichotomique pour ce problème en énumérant de façon exhaustive les instances polynomiales de celui-ci.
Fichier non déposé

Dates et versions

tel-01747275 , version 1 (29-03-2018)

Identifiants

  • HAL Id : tel-01747275 , version 1

Accès intranet

Citer

Laurent Juban. Sur les problèmes de complexité en déduction automatique : base de Hilbert, modèles uniques et minimaux. Autre [cs.OH]. Université Henri Poincaré - Nancy 1, 1999. Français. ⟨NNT : 1999NAN10254⟩. ⟨tel-01747275⟩
44 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More