La réduction du cycle hamiltonien dirigé vers la coloration de graphe

Question

Le problème 3-SAT peut être réduit à la fois la coloration de graphe et le problème du cycle hamiltonien dirigée, mais il est toute chaîne de réductions qui réduisent dirigé le cycle hamiltonien de coloration graphique en temps polynomial?

Answer 1

Soit $ Q \ in \ sf {NP} $ et $ Q » \ in \ {sf le texte NP de {-}} dur $. Ensuite, par définition, $ Q $ est (beaucoup un) réductibles à $ Q '$ en temps polynomial.

La chaîne exacte des réductions dépendra du $ \ {sf NP \ texte {-} dur} $ preuve de ness $ 'Q $. En règle générale, il est prouvé par une chaîne de réductions à partir de $ \ mathrm {SAT} $ et se terminant par $ Q '$, puis en utilisant la balise Cook-Levin théorème. Ainsi, la chaîne de réductions sera une réduction de $ Q $ à $ \ mathrm {SAT} $ suivi de la chaîne de réductions de $ \ mathrm {SAT} $ à $ '$ Q.

Il y a habituellement une réduction plus directe pour les problèmes spécifiques de (sans utiliser Cook-Levin), car il est généralement facile de trouver une formule propositionnelle exprimant directement la propriété requise (sans référence à TMs). Par exemple, dans le cas de Directed Hamiltionian chemin ($ \ mathrm {} $ DHP) et graphique Coloring ($ \ mathrm {GC} $), vous pouvez réduire:

• $ \ mathrm {} DHP $ à $ \ mathrm {SAT} $,
• $ \ mathrm {SAT} $ à $ \ mathrm {3SAT} $,
• $ \ mathrm {} 3SAT $ à $ \ mathrm {GC} $.