Reduzierende den gerichteten Hamiltonschen Zyklus auf Grafikfärbung

Question

Das 3-SAT-Problem kann sowohl auf die Grafikfärbung als auch auf das gerichtete Hamiltonsche Zyklusproblem reduziert werden. Gibt es jedoch eine Kette von Reduktionen, die den gerichteten Hamiltonschen Zyklus reduzieren, um die Farbgebung in der Polynomzeit zu färben?

Answer 1

Sei $ q in sf {np} $ und $ q ' in sf {np text {-} hard} $. Dann ist $ q $ per Definition (viele) in Polynomzeit auf $ q '$ reduzierbar.

Die genaue Kette der Reduzierungen hängt vom $ sf {np text {-} hard} $ ness Proof von $ q '$ ab. Normalerweise wird es durch eine Kette von Reduktionen von $ math {sat} $ und endet mit $ q '$ und dann die Verwendung der Verwendung des Cook-Levin Satz. Die Reduktionskette wird also eine Reduzierung von $ q $ $ mathrm {SAT} $ sein, gefolgt von der Kette der Reduktionen von $ math {SAT} $ bis $ q '$.

In der Regel gibt es eine direktere Reduzierung spezifischer Probleme (ohne die Verwendung von Cook-Levin), da es normalerweise einfach ist, eine Aussageformel zu finden, die die erforderliche Eigenschaft direkt ausdrückt (ohne Bezugnahme auf TMS). Beispielsweise können Sie im Falle eines gerichteten Hamiltionianischen Pfades ($ mathp {DHP} $) und Graph Färbung ($ mathrm {gc} $) reduzieren:

• $ mathhrm {dhp} $ bis $ mathrm {sat} $,
• $ mathhrm {sat} $ bis $ mathhrm {3sat} $,
• $ mathhrm {3sat} $ bis $ mathhrm {gc} $.