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
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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.
Type de document :
Communication dans un congrès
H. Ganzinger, D. McAllister, & A. Voronkov. 6th International Conference on Logic for Programming & Automated Reasoning - LPAR'99, Sep 1999, Tbilisi, Georgia, Springer-Verlag, 1705, pp.13-32, 1999, Lecture Notes in Computer Science (in Artificial Intelligence)
Liste complète des métadonnées

https://hal.inria.fr/inria-00098753
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:33:11
Dernière modification le : mercredi 17 octobre 2018 - 19:50:49

Identifiants

  • HAL Id : inria-00098753, version 1

Collections

Citation

Miki Hermann, Laurent Juban, Phokion G. Kolaitis. On the complexity of counting the Hilbert basis of a linear Diophantine system. H. Ganzinger, D. McAllister, & A. Voronkov. 6th International Conference on Logic for Programming & Automated Reasoning - LPAR'99, Sep 1999, Tbilisi, Georgia, Springer-Verlag, 1705, pp.13-32, 1999, Lecture Notes in Computer Science (in Artificial Intelligence). 〈inria-00098753〉

Partager

Métriques

Consultations de la notice

83