On the Complexity of Counting the Hilbert Basis of a Linear Diophnatine System
On the Complexity of Counting the Hilbert Basis of a Linear Diophnatine System
复制标题
DOI：
10.1007/3-540-48242-3_2
复制
发表时间：
1999-09
期刊：
影响因子：
--
通讯作者：
M. Hermann;L. Juban;Phokion G. Kolaitis
中科院分区：
文献类型：
--
作者：
M. Hermann;L. Juban;Phokion G. Kolaitis
我们研究了计算线性丢番图方程齐次系统的希尔伯特基的计算复杂性。我们通过证明计算希尔伯特基是#P-hard并且属于#NP类来建立该问题复杂性的下限和上限。此外，我们研究了通过限制系统中变量出现的次数而获得的变体的复杂性。
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.