Riducendo ciclo hamiltoniana diretto alla colorazione dei grafi

Question

Il problema 3-SAT può essere ridotto sia la colorazione dei grafi e il problema ciclo hamiltoniana diretto, ma c'è qualche catena di riduzioni che riducono indirizzato ciclo hamiltoniano di colorazione dei grafi in tempo polinomiale?

Answer 1

Let $ Q \ in \ sf {NP} $ e $ Q' \ in \ sf {text NP \ {-}} $ duro. Poi, per definizione, $ Q $ è (molti-uno) riducibile a $ Q '$ in tempo polinomiale.

La catena esatto delle riduzioni dipenderà dalla sf $ \ {NP \ text {-}} $ duro la prova ness di $ $ Q '. In genere, è dimostrato da una catena di riduzioni a partire da $ \ mathrm {} SAT $ e termina con $ Q '$ e quindi utilizzando il Cook-Levin teorema. Così la catena di riduzioni sarà una riduzione da $ Q $ a $ \ mathrm {} SAT $ seguita dalla catena di riduzioni da $ \ mathrm {} SAT $ a $ $ Q '.

Di solito c'è una riduzione più diretta per problemi specifici (senza l'utilizzo di Cook-Levin), dal momento che di solito è facile trovare una formula proposizionale che esprime direttamente la proprietà richiesta (senza alcun riferimento al TMS). Per esempio, nel caso di Directed Hamiltionian Path ($ \ mathrm {} DHP $) e colorazione dei grafi ($ \ mathrm {CG} $), è possibile ridurre:

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