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

. 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. 1 Introduction and Summary of Results The Hilbert basis of a homogeneous system of linear Diophantine equations over the non-negative integers is the set of all non-zero vectors that are minimal solutions with respect to the pointwise order. This set forms indeed a basis of the space of solutions of the system, that is, every solution can be written as a positive linear combination of vectors from the Hilbert basis, and no member of the Hilbert basis can be expressed as a positive linear combination of other members. Moreover, it is essentially the unique such basis. The ..