P/NP-Problem?
Beim P/NP-Problem geht es soweit ich weiß darum das ein effizienter Algorithmus für ein Problem zum Beispiel die Färbung von Graphen, die Existenz von effizienten Algorithmen für alle anderen Probleme der selben Komplexität impliziert, korrigiert mich gerne falls ich das falsch verstanden habe. Ich verstehe nur gerade nicht wie man die Komplexität eines Problems definiert wenn man nicht den effizientesden Algorithmus kennt? "Ein Problem ist K-schwer wenn sich alle anderen Probleme der Klasse K auf den Algorithmus zur diesem Problem zurückführen lassen", damit beißt sich die Katze aber in den Schwanz du definierst die Komplexität eines Problems K dadurch daß sich alle anderen Probleme der Klasse K auf den den selben Algorithmus zurückzuführen wie unseres Anfangsproblems lassen. Weiterhin stellt sich mir die Frage ob es unendlich viele Probleme einer Komplexitätsklassen oder allgemein unendlich viele Komplexitätsklassen gibt?
2 Antworten
Zunächst hat man die Frage nach sog. NP-schweren Problemen. Ein Problem heißt NP-schwer, wenn man aus einer Lösung für dieses Problem in polynomialer Zeit Lösungen für alle NP-Probleme berechnen kann. Damit ist erstmal nichts gesagt darüber, wie die Lösung für das NP-schwere Problem aussieht, es geht erstmal darum, dass man aus seiner Lösung etwas ableiten kann. Für eine Handvoll von Problemen hat man festgestellt, dass sie NP-schwer sind.
Wenn man das hat, kann man sich mit diesem Wissen an die Lösung des NP-P-Problems machen (genauer: einen Versuch starten, das Problem zu lösen). Das NP-P-Problem ist die Antwort auf die Frage, ob alle Probleme der Komplexitätsklasse NP auch in der Komplexitätsklasse P liegen, ob also P eine echte Teilmenge von NP ist oder ob diese beiden Mengen gleich sind.
Denn: Kann man für ein beliebiges NP-schweres Problem zeigen, dass es in P liegt (es also eine sog. effiziente, weil deterministisch polynomiale Lösung gibt), dann hat man quasi einen Hebel gefunden, mit dem man zeigen kann, dass alle Probleme aus NP in P liegen (denn wenn ich eine polynomiale Lösung für ein NP-schweres Problem gefunden habe, kann ich daraus in polynomialer Zeit eine Lösung für jedes NP-Problem finden und polynomial * polynomial bleibt polynomial). Das ist halt noch nicht gelungen.
Die Frage, ob es "unendlich viele Probleme" in einer Komplexitätsklasse gibt, ist so nicht zu beantworten. Es ist letztlich eine Frage, wie man zwei Probleme unterscheidet. Wenn ich eine Lösung für ein Problem aus der Lösung für ein anderes Problem ableiten kann - sind das dann in Wirklichkeit verschiedene Probleme? Oder ist das alles in Wirklichkeit genau EIN Problem, dass ich nur immer wieder anders formuliere?
Und bei den Komplexitätsklassen ist die Frage ähnlich: Was genau definiere ich als eine Klasse? Es werden immer wieder neue Komplexitätsklassen definiert, die jeweils wieder neue Unterarten haben (P und NP sind ja z. B. über die Schrittzahl also die Zeit definiert, andere Komplexitätsklasse definieren sich über die Speichernutzung u. ä.) - schwer zu sagen, ob es eine mathematische Obergrenze dafür gibt).
Die Definition der Klasse NP ist allerdings eindeutig und gar nicht selbstbezüglich. Ein Entscheidungsproblem gehört zu der Klasse NP, wenn eine Nicht-deterministische Turingmaschine in Polynomialer Zeit eine Lösung findet. Das lässt sich umformulieren zu: Ein Entscheidungsproblem liegt in der Klasse NP, wenn ich für eine gegebene Lösung in polynomialer Zeit prüfen kann, ob diese Lösung richtig ist. Das ist durchaus händelbar. Und ansonsten hat man ja bereits NP-schwere Probleme gefunden (und sogar NP-vollständige, also NP-schwere Probleme, die selber in NP liegen), man muss für ein neues Problem "nur" prüfen, ob man einen (polynomialen) Zusammenhang zwischen dessen Lösungen und einem bekannten NP-schweren Problem finden kann.
Du erkennst die Problematik bei P vs. NP. Man weiß bisher nicht, ob nicht ein effizienterer Algorithmus existiert, durch den die Probleme, die NP-schwer sind auch in P lägen.
Weiterhin stellt sich mir die Frage ob es unendlich viele Probleme einer Komplexitätsklassen oder allgemein unendlich viele Komplexitätsklassen gibt?
Ja und jein. Letzteres hängt auch davon ab, was du unter "Komplexitätsklasse" verstehst. Es lassen sich Probleme finden, die zwar effizient lösbar wären, damit fest in einer niedrigeren Komplexitätsklasse liegen, für die man aber Algorithmen schreiben könnte, die beliebig ineffizient sind und somit in beliebigen Komplexitätsklassen lägen, wodurch man sich entsprechend viele Komplexitätsklassen schaffen kann.
Ich würde mich aber nicht darauf festlegen, ob es auch Probleme gäbe, die tatsächlich in diesen Komplexitätsklassen lägen, für die es somit keinen effizienteren Algorithmus gäbe.