Skip to Main content Skip to Navigation
Journal articles

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

Arnaud Durand 1 Miki Hermann 2 Laurent Juban 2
2 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : The problem of computing the Hilbert basis of a homogeneous 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 show that, from the complexity standpoint, it is not important to know the underlying homogeneous linear Diophantine system when we ask whether a given set of vectors constitutes a Hilbert basis.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/inria-00100710
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 2:49:54 PM
Last modification on : Friday, February 26, 2021 - 3:28:05 PM

Identifiers

  • HAL Id : inria-00100710, version 1

Collections

Citation

Arnaud Durand, Miki Hermann, Laurent Juban. On the Complexity of Recognizing the Hilbert Basis of a Linear Diophantine System. Theoretical Computer Science, Elsevier, 2002, 270 (1-2), pp.625-642. ⟨inria-00100710⟩

Share

Metrics

Record views

156