Was ist das P=NP Problem?

P und NP sind beides Komplexitätsklassen der Informatik.

P ist die Klasse der Entscheidungsprobleme (also Probleme wo nur ein ja oder nein gefordert wird, also "kann man dieses Problem lösen?", Wenn die Eingabe ein Problem ist), die in deterministischer Polynom Keller Zeit durchführbar sind. Deterministisch bedeutet, dass das Programm, welches das Problem entscheiden muss, keine Ratephase hat, man kann also eindeutig Vorhersagen, was der nächste Zustand vom Programm ist.

Polynomialzeit bedeutet, dass die Abfolge von Rechenschritte, sich durch ein Polynom der Form n^k nach oben abschätzen lässt. n ist dabei die Größe des Problems (hier ist es die Bitlänge der Eingabe), k ist eine Konstante Zahl

NP ist die Klasse der Entscheidungsprobleme, die in einer nichtdeterimistischen Polynomialzeit lösbar sind.

Solche Algorithmen laufen denn so ab:

1. Die Eingabe des Problems wird eingelesen und geprüft ob sie Syntaktisch Richtig ist.

2. Es wird eine mögliche Lösung geraten

3. Es wird geprüft ob diese Lösung das Problem Löst, wenn ja dann wird ja ausgegeben, wenn nein, dann nein.

Wichtig ist, dass man beim 2. Schritt davon ausgeht, dass das Programm IMMER die richtige Lösung rät, wenn es die gibt.

Ein Problem ist dann in der Klasse NP wenn diese 3 Schritte in Polynomieller Zeit durchgeführt werden.

P und NP sind also Mengen von Problemstellungen, P=NP ist also die Frage, ob beide Mengen gleich sind, also ob es für Probleme der Klasse NP ein Algorithmus der Klasse P existiert. (dass P in NP enthalten ist, ist trivial)

Als Beispiel das Entscheidungsproblem PARTITION:

Man hat eine endliche Anzahl von Zahlen, die Frage ist nun, ob man die Menge der Zahlen in Zwei Mengen disjunkt zerlegen kann (also dass jede Zahl in genau eine der beiden Mengen landet), sodass die Summe der beiden Mengen identisch ist.

Dieses Problem ist in der Klasse NP.

Es ist sogar NP-Hart: jedes Problem der Klasse NP lässt sich auf PARTITION in Polynomieller Zeit reduzieren, sodass das Problem genau dann lösbar ist, wenn die reduzierte Form von Partition lösbar ist.

NP-Hart bedeutet sozusagen, dass das kein Problem der Klasse NP schwerer als dieses Problem ist.

Da das Problem in NP ist und NP hart ist, ist es somit NP vollständig

Das ist eine Frage aus der Philosophie des Programmierens von Computern.

NP heisst "Nichtdeterministisch polynomialzeitlich vollständig". Ein typisches NP-Problem ist ein OL-Lauf: Du musst eine bestimmte Anzahl von Posten anlaufen. Du kennst die Abstände zwischen diesen Posten. Finde den kürzesten Weg, bei dem du alle Posten anläufst.

Bei einer kleinen Anzahl von Posten ist die Aufgabe einfach. Aber bei jedem zusätzliche Posten vervielfacht sich die Anzahl der möglichen Wege. Die Anzahl der möglichen Wege wächst exponentiell.

Auf der anderen Seite gibt es Probleme, die 'einfach' zu lösen sind. Z. B. wenn du die Stempelkarte des OL-Läufers kontrollieren musst, wird der Aufwand auch bei jedem zusätzlichen Posten grösser. Aber der Aufwand für den 20-sten Posten ist gleich gross wie der Aufwand für den 100-sten Posten.

Beim P=NP Problem geht es um die Frage, ob man die schwierigen Aufgaben in einfache umwandeln kann.

Ist lange her, dass ich das gelesen habe, ich hab's nicht mehr genau im Kopf. Ausführlich und sehr unterhaltsam erklärt findest du dies -neben vielen anderen kniffligen Rätseln- bei William Poundstone, 'Im Labyrinth des Denkens'.