Warum ist das P=NP Problem so schwer?
Und welche Ansatzpunkte hat man, um eventuell die Antwort zu bekommen?
3 Antworten
Es gibt 3 Möglichkeiten. Es ist wahr, nicbt wahr oder nicht entscheidbar( nicht entscheidbarkeit habe ich immer noch nicht ganz Verstanden). Um zu zeigen, dass es wahr ist, müsstest du eine Polyzeit reduktion von einem Np-vollständigem Problem auf eines in P finden. Ist anscheinend ziemlich schwer. Um zu zeigen, dass P!=NP müsstest du z.B. P=NP auf einen Widerspruch zurückführen, was anscheinend auch nicht so leicht ist. Ich habe aber erst eine einzige Veranstaltung zur Komplexitätstheorie gehört. Für umfangreichere Antworten und ein tieferes Verständnis musst du auf andere Antworten warten, da ich mehr nicht weiß.
P = alle Probleme die schnell lösbar sind
NP = alle Probleme, bei denen Lösungen schnell auf Korrektheit überprüfbar sind
Was man natürlich weiß, ist dass alle Probleme die schnell lösbar sind, auch schnell überprüfbar sind, also weiß man, dass P eine Teilmenge von NP ist.
Was man nicht weiß, ist ob es ein Problem in NP gibt, was nicht in P ist. Um das zu zeigen müsste man ein Problem finden, für das man schnell eine Lösung auf Korrektheit überprüfen kann, aber nicht schnell eine Lösung finden kann. Das schwierige dabei ist, dass man beweisen muss, dass nicht schnell eine Lösung gefunden werden kann. So ein Problem wurde noch nicht gefunden.
Naja weil bislang keiner eine Lösung gefunden hat. Kann auch sein dass das Problem extrem trivial ist und man einfach noch nicht darauf kam.