On the complexity of recognizing the Hilbert basis of a linear Diophantine system

Abstract : The problem of computing the Hilbert basis of a linear Diophantine system over nonnegative integers is often considered in automated deduction and integer programming. In automated deduction, the Hilbert basis of a corresponding system serves to compute the minimal complete set of associative-commutative unifiers, whereas in integer programming the Hilbert bases are tightly connected to integer polyhedra and to the notion of total dual integrality. In this paper, we sharpen the previously known result that the problem, asking whether a given solution belongs to the Hilbert basis of a given system, is coNP-complete. We show that the problem has a pseudopolynomial algorithm if the number of equations in the system is fixed, but it is coNP-complete in the strong sense if the given system is unbounded. This result is important in the scope of automated deduction, where the input is given in unary and therefore the previously known coNP-completeness result was unusable. Moreover, we prove that, given a linear Diophantine system and a set of solutions, asking whether this set constitutes the Hilbert basis of the system, is also coNP-complete in the strong sense, answering this way an open problem formulated by Henk and Weismantel in 1996. Our result also allows us to solve another open problem, formulated by Edmonds and Giles in 1982, where we prove that asking whether a given set of vectors constitutes the Hilbert basis of an unknown linear Diophantine system, is coNP-complete in the strong sense.
Type de document :
Communication dans un congrès
M. Kutylowski, L. Pacholski, T. Wierzbicki. 24th International Symposium on Mathematical Foundations of Computer Science - MFCS'99, 1999, Szklarska Poreba, Poland, Springer-Verlag, 1672, pp.92-102, 1999, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00098956
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:40:48
Dernière modification le : lundi 5 février 2018 - 11:04:02

Identifiants

  • HAL Id : inria-00098956, version 1

Collections

Citation

Arnaud Durand, Miki Hermann, Laurent Juban. On the complexity of recognizing the Hilbert basis of a linear Diophantine system. M. Kutylowski, L. Pacholski, T. Wierzbicki. 24th International Symposium on Mathematical Foundations of Computer Science - MFCS'99, 1999, Szklarska Poreba, Poland, Springer-Verlag, 1672, pp.92-102, 1999, Lecture Notes in Computer Science. 〈inria-00098956〉

Partager

Métriques

Consultations de la notice

159