J
Das zweite Buch ist auf jeden Fall sehr gut. Es ist ein umfangreiches Kompendium von NP-schweren Problemen. Natürlich ist es bei weitem nicht vollständig. Aber es enthält mit Sicherheit die wichtigsten Probleme und sehr viele Verweise. Zumindest wenn man beweisen will, dass etwas NP-schwer ist, und man keinen Ansatz hat, dann lohnt es sich auf jeden Fall mal darin zu blättern. Den enormen Einfluss dieses Buches sieht man auch an der Zahl der Zitationen. Laut google scholar derzeit 46339 Das ist schon ne Hausnummer.
Aber zurück zum Thema NP-schwer vs. NP-vollständig. Eine Frage, die ich gerne stelle ist die Frage nach euklidischem minimalem Spannbaum. Also was ist die Komplexität folgenden Problems: Gegeben eine Menge von Punkten im R^2 (mit rationalen Koordinaten), berechne einen miminalen Spannbaum. Genauer gesagt: Ist dieses Problem in NP? -- Klar, jeder Informatiker der was auf sich hält kennt die Antwort. Mittels Kruskal-Algorithmus kann man den MST ausrechnen und damit ist das Problem in P.
Aber jetzt kommt die große Überraschung: Es ist nichtmal klar ob das Problem in NP ist. Das obige Argument ist nicht falsch, wir können den minimalen Spannbaum tatsächlich in polynomieller Zeit bestimmen: Sortiere die Kanten nach Länge (am besten nach quadrat der Länge, das ist dasselbe aber braucht keine wurzeln), dann gehe greedy vor und nimm Kanten dazu, die keine Kreise erzeugen. Dummerweise geht das aber an der NP-Frage vorbei. Die Klasse NP ist eine Klasse von Entscheidungsproblemen: Die richtige Frage lautet also, gegeben n Punkte im R^2 (mit rationalen Koordinaten) und eine rationale Zahl b, gibt es einen Spannbaum mit Gesamtlänge kleiner oder gleich b. Natürlich können wir wie zuvor beschrieben den kürzesten Spannbaum ausrechnen. Das große Problem ist die Länge mit b zu vergleichen. Die Länge des Spannbaums ist nämlich eine Summe von n-1 Wurzeln von rationalen Zahlen, die mit einer rationalen Zahl verglichen werden sollen. Gelingt uns das, so ist damit nachgewiesen dass das Problem in NP ist, geht das aber nicht effizient, dann ist das Problem nicht in NP. Und genau diese Frage, ob man eine Summe von Wurzeln rationaler Zahlen effizient mit einer rationalen Zahl vergleichen kann ist ein großes offenes Problem.
Beim TSP und letztlich bei sehr vielen Problemen in denen Geometrie vorkommt, ist deshalb häufig nicht so leicht zu klären, ob sie nun in NP liegen oder nicht.