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

DOI10.1016/S0304-3975(01)00017-2MaRDI QIDQ5958323zbMATH OpenFDO

Authors Arnaud Durand, Miki Hermann, Laurent Juban

Publication date 3 March 2002

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(01)00017-2

zbMATH Keywords

completeness in the strong sensecomputational complexitycoNP-completenessHilbert basishomogeneous linear Diophantine system

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Publication:4941892
• NP-completeness conditions for consistency verification of some types of systems of linear Diophantine dis-equations
• scientific article; zbMATH DE number 1405441
• Recognizing conic TDI systems is hard
• On computing Hilbert bases via the Elliot--MacMahon algorithm

Cites work

• A Unification Algorithm for Associative-Commutative Functions
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3995771 (Why is no real title available?)
• scientific article; zbMATH DE number 1405441 (Why is no real title available?)
• On the complexity of integer programming
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix

Cited in

(4)

• scientific article; zbMATH DE number 1405441 (Why is no real title available?)
• scientific article; zbMATH DE number 1418330 (Why is no real title available?)
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• The complexity of almost linear diophantine problems

This page was built for publication: On the complexity of recognizing the Hilbert basis of a linear Diophantine system

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5958323)