https://minerve.ens-rennes.fr/index.php?action=history&feed=atom&title=Garey-Johnson 2026-05-07T02:21:30Z Historique pour cette page sur le wiki MediaWiki 1.24.0 https://minerve.ens-rennes.fr/index.php?title=Garey-Johnson&diff=3675&oldid=prev 2019-02-04T23:09:11Z

<p></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Version précédente</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Version du 4 février 2019 à 23:09</td> </tr><tr><td colspan="2" class="diff-lineno">Ligne 10 :</td> <td colspan="2" class="diff-lineno">Ligne 10 :</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&#160; Référence (et parfois le nom du problème vers lequel faire la réduction pour montrer la NP-dureté)</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&#160; Référence (et parfois le nom du problème vers lequel faire la réduction pour montrer la NP-dureté)</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&#160; Commentaire (des variantes du problèmes ou des choses du genre : &quot;ça reste NP-complet même quand on restreint les instances à ...&quot;)</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&#160; Commentaire (des variantes du problèmes ou des choses du genre : &quot;ça reste NP-complet même quand on restreint les instances à ...&quot;)</div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">David X</ins></div></td></tr> </table>

David X https://minerve.ens-rennes.fr/index.php?title=Garey-Johnson&diff=3670&oldid=prev 2019-02-04T23:01:26Z

<p></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Version précédente</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Version du 4 février 2019 à 23:01</td> </tr><tr><td colspan="2" class="diff-lineno">Ligne 9 :</td> <td colspan="2" class="diff-lineno">Ligne 9 :</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&#160; Question (question fermée car ce sont des problèmes de décision)</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&#160; Question (question fermée car ce sont des problèmes de décision)</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&#160; Référence (et parfois le nom du problème vers lequel faire la réduction pour montrer la NP-dureté)</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&#160; Référence (et parfois le nom du problème vers lequel faire la réduction pour montrer la NP-dureté)</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#160; Commentaire (<del class="diffchange diffchange-inline">souvent </del>des variantes du problèmes ou des choses du genre : &quot;<del class="diffchange diffchange-inline">le problème </del>reste NP-complet <del class="diffchange diffchange-inline">lorsque l'</del>on restreint les instances à ...&quot;)</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#160; Commentaire (des variantes du problèmes ou des choses du genre : &quot;<ins class="diffchange diffchange-inline">ça </ins>reste NP-complet <ins class="diffchange diffchange-inline">même quand </ins>on restreint les instances à ...&quot;)</div></td></tr> </table>

David X https://minerve.ens-rennes.fr/index.php?title=Garey-Johnson&diff=3669&oldid=prev 2019-02-04T23:00:52Z

<p></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Version précédente</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Version du 4 février 2019 à 23:00</td> </tr><tr><td colspan="2" class="diff-lineno">Ligne 5 :</td> <td colspan="2" class="diff-lineno">Ligne 5 :</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Les problèmes sont rangés dans 12 catégories (théorie des graphes, réseaux, ensembles et partitions et autres).</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Les problèmes sont rangés dans 12 catégories (théorie des graphes, réseaux, ensembles et partitions et autres).</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Chaque problème est présenté de la manière suivante : &#160;</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Chaque problème est présenté de la manière suivante : &#160;</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">&#160; </del>Nom du problème</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> </ins>Nom du problème</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">&#160; </del>Instance du problème</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> </ins>Instance du problème</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">&#160; </del>Question (question fermée car ce sont des problèmes de décision)</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> </ins>Question (question fermée car ce sont des problèmes de décision)</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">&#160; </del>Référence (et parfois le nom du problème vers lequel faire la réduction pour montrer la NP-dureté)</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> </ins>Référence (et parfois le nom du problème vers lequel faire la réduction pour montrer la NP-dureté)</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">&#160; </del>Commentaire (souvent des variantes du problèmes ou des choses du genre : &quot;le problème reste NP-complet lorsque l'on restreint les instances à ...&quot;)</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> </ins>Commentaire (souvent des variantes du problèmes ou des choses du genre : &quot;le problème reste NP-complet lorsque l'on restreint les instances à ...&quot;)</div></td></tr> </table>

David X https://minerve.ens-rennes.fr/index.php?title=Garey-Johnson&diff=3668&oldid=prev 2019-02-04T23:00:39Z

<p></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Version précédente</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Version du 4 février 2019 à 23:00</td> </tr><tr><td colspan="2" class="diff-lineno">Ligne 5 :</td> <td colspan="2" class="diff-lineno">Ligne 5 :</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Les problèmes sont rangés dans 12 catégories (théorie des graphes, réseaux, ensembles et partitions et autres).</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Les problèmes sont rangés dans 12 catégories (théorie des graphes, réseaux, ensembles et partitions et autres).</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Chaque problème est présenté de la manière suivante : &#160;</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Chaque problème est présenté de la manière suivante : &#160;</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">&#160; &#160; </del>Nom du problème</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">&#160; </ins>Nom du problème</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">&#160; &#160; </del>Instance du problème</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">&#160; </ins>Instance du problème</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">&#160; &#160; </del>Question (question fermée car ce sont des problèmes de décision)</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">&#160; </ins>Question (question fermée car ce sont des problèmes de décision)</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">&#160; &#160; </del>Référence (et parfois le nom du problème vers lequel faire la réduction pour montrer la NP-dureté)</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">&#160; </ins>Référence (et parfois le nom du problème vers lequel faire la réduction pour montrer la NP-dureté)</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">&#160; &#160; </del>Commentaire (souvent des variantes du problèmes ou des choses du genre : &quot;le problème reste NP-complet lorsque l'on restreint les instances à ...&quot;)</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">&#160; </ins>Commentaire (souvent des variantes du problèmes ou des choses du genre : &quot;le problème reste NP-complet lorsque l'on restreint les instances à ...&quot;)</div></td></tr> </table>

David X https://minerve.ens-rennes.fr/index.php?title=Garey-Johnson&diff=3667&oldid=prev 2019-02-04T23:00:26Z

<p></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Version précédente</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Version du 4 février 2019 à 23:00</td> </tr><tr><td colspan="2" class="diff-lineno">Ligne 5 :</td> <td colspan="2" class="diff-lineno">Ligne 5 :</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Les problèmes sont rangés dans 12 catégories (théorie des graphes, réseaux, ensembles et partitions et autres).</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Les problèmes sont rangés dans 12 catégories (théorie des graphes, réseaux, ensembles et partitions et autres).</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Chaque problème est présenté de la manière suivante : &#160;</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Chaque problème est présenté de la manière suivante : &#160;</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#160;&#160; &#160; <del class="diffchange diffchange-inline">- </del>Nom du problème</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#160;&#160; &#160; Nom du problème</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#160;&#160; &#160; <del class="diffchange diffchange-inline">- </del>Instance du problème</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#160;&#160; &#160; Instance du problème</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#160;&#160; &#160; <del class="diffchange diffchange-inline">- </del>Question (question fermée car ce sont des problèmes de décision)</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#160;&#160; &#160; Question (question fermée car ce sont des problèmes de décision)</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#160;&#160; &#160; <del class="diffchange diffchange-inline">- </del>Référence (et parfois le nom du problème vers lequel faire la réduction pour montrer la NP-dureté)</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#160;&#160; &#160; Référence (et parfois le nom du problème vers lequel faire la réduction pour montrer la NP-dureté)</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#160;&#160; &#160; <del class="diffchange diffchange-inline">- </del>Commentaire (souvent des variantes du problèmes ou des choses du genre : &quot;le problème reste NP-complet lorsque l'on restreint les instances à ...&quot;)</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#160;&#160; &#160; Commentaire (souvent des variantes du problèmes ou des choses du genre : &quot;le problème reste NP-complet lorsque l'on restreint les instances à ...&quot;)</div></td></tr> </table>

David X https://minerve.ens-rennes.fr/index.php?title=Garey-Johnson&diff=3666&oldid=prev 2019-02-04T23:00:02Z

<p>Page créée avec « Un bestiaire de problèmes NP-complets avec des références vers les livres ou articles où les démonstrations de NP-complétude sont faites (sauf pour les problèmes cl... »</p> <p><b>Nouvelle page</b></p><div>Un bestiaire de problèmes NP-complets avec des références vers les livres ou articles où les démonstrations de NP-complétude sont faites (sauf pour les problèmes classiques comme SAT, 3SAT, VERTEX-COVER, CLIQUE, HAMILTONIAN-CIRCUIT etc. dont les réductions sont présentées directement dans le livre). Par contre, ces preuves ne sont pas très faciles à lire, il vaut peut-être mieux se référer à d'autres ouvrages pour cela.<br /> <br /> Mais ce livre fournit une liste impressionnante de potentiels développements (qui rentrent au moins dans la leçon sur la NP-complétude) !<br /> <br /> Les problèmes sont rangés dans 12 catégories (théorie des graphes, réseaux, ensembles et partitions et autres).<br /> Chaque problème est présenté de la manière suivante : <br /> - Nom du problème<br /> - Instance du problème<br /> - Question (question fermée car ce sont des problèmes de décision)<br /> - Référence (et parfois le nom du problème vers lequel faire la réduction pour montrer la NP-dureté)<br /> - Commentaire (souvent des variantes du problèmes ou des choses du genre : &quot;le problème reste NP-complet lorsque l'on restreint les instances à ...&quot;)</div>

David X