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

摘要

We investigate the computational complexity of counting the Hibert basis of a homogeneous system of linear Diophantine equations. We establish lower and upper bounds on the complexity of this problem by showign 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.