On the complexity of recognizing the Hilbert basis of a linear Diophantine system
Identifieur interne :
000A92 ( PascalFrancis/Corpus );
précédent :
000A91;
suivant :
000A93
On the complexity of recognizing the Hilbert basis of a linear Diophantine system
Auteurs : A. Durand ;
M. Hermann ;
L. JubanSource :
-
Lecture notes in computer science [ 0302-9743 ] ; 1999.
RBID : Pascal:99-0505435
Descripteurs français
English descriptors
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.
Notice en format standard (ISO 2709)
Pour connaître la documentation sur le format Inist Standard.
| pA |
| A01 | 01 | 1 | | @0 0302-9743 |
|---|
| A05 | | | | @2 1672 |
|---|
| A08 | 01 | 1 | ENG | @1 On the complexity of recognizing the Hilbert basis of a linear Diophantine system |
|---|
| A09 | 01 | 1 | ENG | @1 MFCS '99 : mathematical foundations of computer science : Szklarska Poręba, 6-10 September 1999 |
|---|
| A11 | 01 | 1 | | @1 DURAND (A.) |
|---|
| A11 | 02 | 1 | | @1 HERMANN (M.) |
|---|
| A11 | 03 | 1 | | @1 JUBAN (L.) |
|---|
| A12 | 01 | 1 | | @1 KUTYOWSKI (Mirosłalw) @9 ed. |
|---|
| A12 | 02 | 1 | | @1 PACHOLSKI (Leszek) @9 ed. |
|---|
| A12 | 03 | 1 | | @1 WIERZBICKI (Tomasz) @9 ed. |
|---|
| A14 | 01 | | | @1 LACL, Department of Computer Science, Université Paris 12, 61, av. gen. de Gaule @2 94010 Créteil @3 FRA @Z 1 aut. |
|---|
| A14 | 02 | | | @1 LORIA (CNRS and Université Henri Poincaré Nancy 1), BP 239 @2 54506, Vandœuvre-lès-Nancy @3 FRA @Z 2 aut. @Z 3 aut. |
|---|
| A20 | | | | @1 92-102 |
|---|
| A21 | | | | @1 1999 |
|---|
| A23 | 01 | | | @0 ENG |
|---|
| A26 | 01 | | | @0 3-540-66408-4 |
|---|
| A43 | 01 | | | @1 INIST @2 16343 @5 354000084584660090 |
|---|
| A44 | | | | @0 0000 @1 © 1999 INIST-CNRS. All rights reserved. |
|---|
| A45 | | | | @0 17 ref. |
|---|
| A47 | 01 | 1 | | @0 99-0505435 |
|---|
| A60 | | | | @1 P @2 C |
|---|
| A61 | | | | @0 A |
|---|
| A64 | 01 | 1 | | @0 Lecture notes in computer science |
|---|
| A66 | 01 | | | @0 DEU |
|---|
| C01 | 01 | | ENG | @0 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. |
|---|
| C02 | 01 | X | | @0 001D02A03 |
|---|
| C02 | 02 | X | | @0 001D02C05 |
|---|
| C03 | 01 | X | FRE | @0 Programmation en nombres entiers @5 01 |
|---|
| C03 | 01 | X | ENG | @0 Integer programming @5 01 |
|---|
| C03 | 01 | X | SPA | @0 Programación entera @5 01 |
|---|
| C03 | 02 | X | FRE | @0 Système linéaire @5 02 |
|---|
| C03 | 02 | X | ENG | @0 Linear system @5 02 |
|---|
| C03 | 02 | X | SPA | @0 Sistema lineal @5 02 |
|---|
| C03 | 03 | X | FRE | @0 Equation diophantienne @5 03 |
|---|
| C03 | 03 | X | ENG | @0 Diophantine equation @5 03 |
|---|
| C03 | 03 | X | SPA | @0 Ecuación diofántica @5 03 |
|---|
| C03 | 04 | X | FRE | @0 Système équation @5 04 |
|---|
| C03 | 04 | X | ENG | @0 Equation system @5 04 |
|---|
| C03 | 04 | X | SPA | @0 Sistema ecuación @5 04 |
|---|
| C03 | 05 | X | FRE | @0 Reconnaissance @5 05 |
|---|
| C03 | 05 | X | ENG | @0 Recognition @5 05 |
|---|
| C03 | 05 | X | SPA | @0 Reconocimiento @5 05 |
|---|
| C03 | 06 | X | FRE | @0 Problème NP complet @5 06 |
|---|
| C03 | 06 | X | ENG | @0 NP complete problem @5 06 |
|---|
| C03 | 06 | X | SPA | @0 Problema NP completo @5 06 |
|---|
| C03 | 07 | X | FRE | @0 Résolution système équation @5 07 |
|---|
| C03 | 07 | X | ENG | @0 Equation system solving @5 07 |
|---|
| C03 | 07 | X | SPA | @0 Resolución sistema ecuación @5 07 |
|---|
| C03 | 08 | X | FRE | @0 Complexité @5 08 |
|---|
| C03 | 08 | X | ENG | @0 Complexity @5 08 |
|---|
| C03 | 08 | X | SPA | @0 Complejidad @5 08 |
|---|
| C03 | 09 | X | FRE | @0 Calcul automatique @5 09 |
|---|
| C03 | 09 | X | ENG | @0 Computing @5 09 |
|---|
| C03 | 09 | X | SPA | @0 Cálculo automático @5 09 |
|---|
| C03 | 10 | X | FRE | @0 Base Hilbert @4 INC @5 72 |
|---|
| N21 | | | | @1 326 |
|---|
|
|---|
| pR |
| A30 | 01 | 1 | ENG | @1 Mathematical foundations of computer science. International symposium @2 24 @3 Szklarska Poręba POL @4 1999-09-06 |
|---|
|
|---|
Format Inist (serveur)
| NO : | PASCAL 99-0505435 INIST |
|---|
| ET : | On the complexity of recognizing the Hilbert basis of a linear Diophantine system |
|---|
| AU : | DURAND (A.); HERMANN (M.); JUBAN (L.); KUTYOWSKI (Mirosłalw); PACHOLSKI (Leszek); WIERZBICKI (Tomasz) |
|---|
| AF : | LACL, Department of Computer Science, Université Paris 12, 61, av. gen. de Gaule/94010 Créteil/France (1 aut.); LORIA (CNRS and Université Henri Poincaré Nancy 1), BP 239/54506, Vandœuvre-lès-Nancy/France (2 aut., 3 aut.) |
|---|
| DT : | Publication en série; Congrès; Niveau analytique |
|---|
| SO : | Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 1999; Vol. 1672; Pp. 92-102; Bibl. 17 ref. |
|---|
| LA : | Anglais |
|---|
| EA : | 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. |
|---|
| CC : | 001D02A03; 001D02C05 |
|---|
| FD : | Programmation en nombres entiers; Système linéaire; Equation diophantienne; Système équation; Reconnaissance; Problème NP complet; Résolution système équation; Complexité; Calcul automatique; Base Hilbert |
|---|
| ED : | Integer programming; Linear system; Diophantine equation; Equation system; Recognition; NP complete problem; Equation system solving; Complexity; Computing |
|---|
| SD : | Programación entera; Sistema lineal; Ecuación diofántica; Sistema ecuación; Reconocimiento; Problema NP completo; Resolución sistema ecuación; Complejidad; Cálculo automático |
|---|
| LO : | INIST-16343.354000084584660090 |
|---|
| ID : | 99-0505435 |
|---|
Links to Exploration step
Pascal:99-0505435
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">On the complexity of recognizing the Hilbert basis of a linear Diophantine system</title>
<author><name sortKey="Durand, A" sort="Durand, A" uniqKey="Durand A" first="A." last="Durand">A. Durand</name>
<affiliation><inist:fA14 i1="01"><s1>LACL, Department of Computer Science, Université Paris 12, 61, av. gen. de Gaule</s1>
<s2>94010 Créteil</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14><author><name sortKey="Hermann, M" sort="Hermann, M" uniqKey="Hermann M" first="M." last="Hermann">M. Hermann</name>
<affiliation><inist:fA14 i1="02"><s1>LORIA (CNRS and Université Henri Poincaré Nancy 1), BP 239</s1>
<s2>54506, Vandœuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14><author><name sortKey="Juban, L" sort="Juban, L" uniqKey="Juban L" first="L." last="Juban">L. Juban</name>
<affiliation><inist:fA14 i1="02"><s1>LORIA (CNRS and Université Henri Poincaré Nancy 1), BP 239</s1>
<s2>54506, Vandœuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14><publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">99-0505435</idno>
<date when="1999">1999</date>
<idno type="stanalyst">PASCAL 99-0505435 INIST</idno>
<idno type="RBID">Pascal:99-0505435</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000A92</idno>
</publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">On the complexity of recognizing the Hilbert basis of a linear Diophantine system</title>
<author><name sortKey="Durand, A" sort="Durand, A" uniqKey="Durand A" first="A." last="Durand">A. Durand</name>
<affiliation><inist:fA14 i1="01"><s1>LACL, Department of Computer Science, Université Paris 12, 61, av. gen. de Gaule</s1>
<s2>94010 Créteil</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14><author><name sortKey="Hermann, M" sort="Hermann, M" uniqKey="Hermann M" first="M." last="Hermann">M. Hermann</name>
<affiliation><inist:fA14 i1="02"><s1>LORIA (CNRS and Université Henri Poincaré Nancy 1), BP 239</s1>
<s2>54506, Vandœuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14><author><name sortKey="Juban, L" sort="Juban, L" uniqKey="Juban L" first="L." last="Juban">L. Juban</name>
<affiliation><inist:fA14 i1="02"><s1>LORIA (CNRS and Université Henri Poincaré Nancy 1), BP 239</s1>
<s2>54506, Vandœuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14><series><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
<imprint><date when="1999">1999</date>
</imprint><seriesStmt><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
</seriesStmt><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Complexity</term>
<term>Computing</term>
<term>Diophantine equation</term>
<term>Equation system</term>
<term>Equation system solving</term>
<term>Integer programming</term>
<term>Linear system</term>
<term>NP complete problem</term>
<term>Recognition</term>
</keywords><keywords scheme="Pascal" xml:lang="fr"><term>Programmation en nombres entiers</term>
<term>Système linéaire</term>
<term>Equation diophantienne</term>
<term>Système équation</term>
<term>Reconnaissance</term>
<term>Problème NP complet</term>
<term>Résolution système équation</term>
<term>Complexité</term>
<term>Calcul automatique</term>
<term>Base Hilbert</term>
</keywords><front><div type="abstract" xml:lang="en">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.</div>
</front><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0302-9743</s0>
</fA01><fA05><s2>1672</s2>
</fA05><fA08 i1="01" i2="1" l="ENG"><s1>On the complexity of recognizing the Hilbert basis of a linear Diophantine system</s1>
</fA08><fA09 i1="01" i2="1" l="ENG"><s1>MFCS '99 : mathematical foundations of computer science : Szklarska Poręba, 6-10 September 1999</s1>
</fA09><fA11 i1="01" i2="1"><s1>DURAND (A.)</s1>
</fA11><fA11 i1="02" i2="1"><s1>HERMANN (M.)</s1>
</fA11><fA11 i1="03" i2="1"><s1>JUBAN (L.)</s1>
</fA11><fA12 i1="01" i2="1"><s1>KUTYOWSKI (Mirosłalw)</s1>
<s9>ed.</s9>
</fA12><fA12 i1="02" i2="1"><s1>PACHOLSKI (Leszek)</s1>
<s9>ed.</s9>
</fA12><fA12 i1="03" i2="1"><s1>WIERZBICKI (Tomasz)</s1>
<s9>ed.</s9>
</fA12><fA14 i1="01"><s1>LACL, Department of Computer Science, Université Paris 12, 61, av. gen. de Gaule</s1>
<s2>94010 Créteil</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</fA14><fA14 i1="02"><s1>LORIA (CNRS and Université Henri Poincaré Nancy 1), BP 239</s1>
<s2>54506, Vandœuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
</fA14><fA20><s1>92-102</s1>
</fA20><fA21><s1>1999</s1>
</fA21><fA23 i1="01"><s0>ENG</s0>
</fA23><fA26 i1="01"><s0>3-540-66408-4</s0>
</fA26><fA43 i1="01"><s1>INIST</s1>
<s2>16343</s2>
<s5>354000084584660090</s5>
</fA43><fA44><s0>0000</s0>
<s1>© 1999 INIST-CNRS. All rights reserved.</s1>
</fA44><fA45><s0>17 ref.</s0>
</fA45><fA47 i1="01" i2="1"><s0>99-0505435</s0>
</fA47><fA60><s1>P</s1>
<s2>C</s2>
</fA60><fA64 i1="01" i2="1"><s0>Lecture notes in computer science</s0>
</fA64><fA66 i1="01"><s0>DEU</s0>
</fA66><fC01 i1="01" l="ENG"><s0>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.</s0>
</fC01><fC02 i1="01" i2="X"><s0>001D02A03</s0>
</fC02><fC02 i1="02" i2="X"><s0>001D02C05</s0>
</fC02><fC03 i1="01" i2="X" l="FRE"><s0>Programmation en nombres entiers</s0>
<s5>01</s5>
</fC03><fC03 i1="01" i2="X" l="ENG"><s0>Integer programming</s0>
<s5>01</s5>
</fC03><fC03 i1="01" i2="X" l="SPA"><s0>Programación entera</s0>
<s5>01</s5>
</fC03><fC03 i1="02" i2="X" l="FRE"><s0>Système linéaire</s0>
<s5>02</s5>
</fC03><fC03 i1="02" i2="X" l="ENG"><s0>Linear system</s0>
<s5>02</s5>
</fC03><fC03 i1="02" i2="X" l="SPA"><s0>Sistema lineal</s0>
<s5>02</s5>
</fC03><fC03 i1="03" i2="X" l="FRE"><s0>Equation diophantienne</s0>
<s5>03</s5>
</fC03><fC03 i1="03" i2="X" l="ENG"><s0>Diophantine equation</s0>
<s5>03</s5>
</fC03><fC03 i1="03" i2="X" l="SPA"><s0>Ecuación diofántica</s0>
<s5>03</s5>
</fC03><fC03 i1="04" i2="X" l="FRE"><s0>Système équation</s0>
<s5>04</s5>
</fC03><fC03 i1="04" i2="X" l="ENG"><s0>Equation system</s0>
<s5>04</s5>
</fC03><fC03 i1="04" i2="X" l="SPA"><s0>Sistema ecuación</s0>
<s5>04</s5>
</fC03><fC03 i1="05" i2="X" l="FRE"><s0>Reconnaissance</s0>
<s5>05</s5>
</fC03><fC03 i1="05" i2="X" l="ENG"><s0>Recognition</s0>
<s5>05</s5>
</fC03><fC03 i1="05" i2="X" l="SPA"><s0>Reconocimiento</s0>
<s5>05</s5>
</fC03><fC03 i1="06" i2="X" l="FRE"><s0>Problème NP complet</s0>
<s5>06</s5>
</fC03><fC03 i1="06" i2="X" l="ENG"><s0>NP complete problem</s0>
<s5>06</s5>
</fC03><fC03 i1="06" i2="X" l="SPA"><s0>Problema NP completo</s0>
<s5>06</s5>
</fC03><fC03 i1="07" i2="X" l="FRE"><s0>Résolution système équation</s0>
<s5>07</s5>
</fC03><fC03 i1="07" i2="X" l="ENG"><s0>Equation system solving</s0>
<s5>07</s5>
</fC03><fC03 i1="07" i2="X" l="SPA"><s0>Resolución sistema ecuación</s0>
<s5>07</s5>
</fC03><fC03 i1="08" i2="X" l="FRE"><s0>Complexité</s0>
<s5>08</s5>
</fC03><fC03 i1="08" i2="X" l="ENG"><s0>Complexity</s0>
<s5>08</s5>
</fC03><fC03 i1="08" i2="X" l="SPA"><s0>Complejidad</s0>
<s5>08</s5>
</fC03><fC03 i1="09" i2="X" l="FRE"><s0>Calcul automatique</s0>
<s5>09</s5>
</fC03><fC03 i1="09" i2="X" l="ENG"><s0>Computing</s0>
<s5>09</s5>
</fC03><fC03 i1="09" i2="X" l="SPA"><s0>Cálculo automático</s0>
<s5>09</s5>
</fC03><fC03 i1="10" i2="X" l="FRE"><s0>Base Hilbert</s0>
<s4>INC</s4>
<s5>72</s5>
</fC03><fN21><s1>326</s1>
</fN21><pR><fA30 i1="01" i2="1" l="ENG"><s1>Mathematical foundations of computer science. International symposium</s1>
<s2>24</s2>
<s3>Szklarska Poręba POL</s3>
<s4>1999-09-06</s4>
</fA30><server><NO>PASCAL 99-0505435 INIST</NO>
<ET>On the complexity of recognizing the Hilbert basis of a linear Diophantine system</ET>
<AU>DURAND (A.); HERMANN (M.); JUBAN (L.); KUTYOWSKI (Mirosłalw); PACHOLSKI (Leszek); WIERZBICKI (Tomasz)</AU>
<AF>LACL, Department of Computer Science, Université Paris 12, 61, av. gen. de Gaule/94010 Créteil/France (1 aut.); LORIA (CNRS and Université Henri Poincaré Nancy 1), BP 239/54506, Vandœuvre-lès-Nancy/France (2 aut., 3 aut.)</AF>
<DT>Publication en série; Congrès; Niveau analytique</DT>
<SO>Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 1999; Vol. 1672; Pp. 92-102; Bibl. 17 ref.</SO>
<LA>Anglais</LA>
<EA>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.</EA>
<CC>001D02A03; 001D02C05</CC>
<FD>Programmation en nombres entiers; Système linéaire; Equation diophantienne; Système équation; Reconnaissance; Problème NP complet; Résolution système équation; Complexité; Calcul automatique; Base Hilbert</FD>
<ED>Integer programming; Linear system; Diophantine equation; Equation system; Recognition; NP complete problem; Equation system solving; Complexity; Computing</ED>
<SD>Programación entera; Sistema lineal; Ecuación diofántica; Sistema ecuación; Reconocimiento; Problema NP completo; Resolución sistema ecuación; Complejidad; Cálculo automático</SD>
<LO>INIST-16343.354000084584660090</LO>
<ID>99-0505435</ID>
</server>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000A92 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000A92 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Corpus
|type= RBID
|clé= Pascal:99-0505435
|texte= On the complexity of recognizing the Hilbert basis of a linear Diophantine system
}}
| This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022 |  |
