We investigate the computational complexity of counting the Hilbert
basis of a homogeneous system of linear Diophantine equations. We
establish lower and upper bounds 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.
Last modified: Tue Jul 20 12:23:12 MET DST 1999