Sur la complexité du comptage et de la reconnaissance de la base de Hilbert d’un système d’équations diophantiennes linéaires homogène

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 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. La classe #P est la classe définie par Valiant qui compte le nombre de solutions de problèmes de la classe NP, tandis que la classe #NP est la classe des fonctions comptant le nombre de solutions de problèmes de la classe NP^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.