NP vollständig
-
Ist es "üblich", daß man wenn man sorum eine Überführung findet, dann auch ein paar Monate später jemand andersrum eine Reduzierung findet?
-
Nein, das ist nicht üblich. Man zeigt üblicherweise (bzw. versucht zu zeigen) dass das Problem in NP ist. Das könnte man tun, indem man es auf ein geeignetes Problem aus NP zurückführt. Aber oft ist es einfacher mit einer äquivalenten Definition von NP zu Arbeiten, nämlich der dass NP alle Probleme enthält für die eine gegebene Lösung in polynomieller Zeit überprüft werden kann -- und genau das zeigt man. Das ist meistens sehr einfach... im Falle von TSP gebe ich Dir eine Tour und behaupte sie habe Länge höchstens k. Du prüfst also nur, ob es eine Tour ist und ob deren Länge höchstens k ist. Das ist ganz leicht in polynomieller Zeit zu bewerkstelligen.
Dadurch weiß man dass das Problem in NP ist weiß man also, dass es sich in polynomieller Zeit in jedes beliebige NP-vollständige Problem transformieren lässt. Eine konkrete Transformation ist dann meist uninteressant. Überhaupt wird die Zugehörigkeit zu NP meist nur sehr knapp behandelt, weil das in den meisten Fällen (wie zuvor skizziert) ziemlich simpel ist. Es gibt allerdings auch einige hartnäckige Fälle von denen man immer noch nicht weiß ob sie zu NP gehören. Da wäre ein Fortschritt sicher gerne gesehen.