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

DOI10.1016/S0304-3975(01)00017-2zbMath0988.68083MaRDI QIDQ5958323

Laurent Juban, Miki Hermann, Arnaud Durand

Publication date: 3 March 2002

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

zbMATH Keywords

computational complexityHilbert basiscompleteness in the strong sensecoNP-completenesshomogeneous linear Diophantine system

Mathematics Subject Classification ID

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

Related Items (1)

The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• A Unification Algorithm for Associative-Commutative Functions
• On the complexity of integer programming

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