On the Complexity of Counting the Hilbert Basis of a Linear Diophantine System

Miki Hermann (1) , Laurent Juban (1) , Phokion G. Kolaitis (2)

1 PROTHEO - Constraints, automatic deduction and software properties proofs
2 Department of Computer Science [Santa Barbara]

We investigate the computational complexity of counting the Hilbert basis of a homogeneous system of linear Diophantine equations. We establish lower and upper bound on 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.

Mots clés: Complexity; Counting problem; Hilbert Basis; Linear Diophantine System; complexité; problème de comptage; base de Hilbert; Système d'équations Diophantienne linéaires

Domaines: Autre [cs.OH]

Miki Hermann, Laurent Juban, Phokion G. Kolaitis. On the Complexity of Counting the Hilbert Basis of a Linear Diophantine System. [Intern report] 98-R-281 || hermann98c, 1998, 16 p. ⟨inria-00098565⟩