Das P = NP-Problem history menue Letztmalig dran rumgefummelt: 28.01.08 18:21:42

1972 griff Richard Karp diese Idee auf und zeigte für 21 verschiedene kombinatorische und graphentheoretische Probleme, die dafür bekannt waren, dass sie sich hartnäckig einer effizienten algorithmischen Lösbarkeit entzogen, dass diese ebenfalls NP-vollständig sind.
Indem er aufzeigte, dass eine große Anzahl von bedeutenden Problemen NP-vollständig sind, motivierte Karp die weitere Erforschung der Klasse NP, der Theorie der NP-Vollständigkeit sowie der Fragestellung, ob die Klassen P und NP identisch sind oder sich unterscheiden (P-NP-Problem). Letzteres zählt heute zu den wichtigsten offenen mathematischen Fragestellungen. Unter anderem zählt es zu den sieben Millennium-Problemen des Clay Mathematics Institute, für deren Lösung Preisgelder von jeweils einer Million US-Dollar ausgelobt wurden.
1. Eigenschaften von Problemklassen
2. Einfache Polynomiale Probleme
3. Entscheidbarkeit
4. NP-vollständige Probleme
5. NP-schwierige Probleme
6. Verwandte Themen

NP-vollständige sowie NP-schwere Probleme

Gretchen-Frage

begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-)

Informatik-Profi-Wissen

Quellen:
„Talente finden Lösungen, Genies entdecken Probleme.“

Krailsheimer

P = NP?

Uns ist kein wissenschaftliches Problem bekannt, das „allumfassender" und dennoch einfacher zu formulieren wäre als die berühmte P=NP-Frage: Grob gesagt geht es hierbei darum zu ergründen, ob eine Vielzahl natürlicher und anwendungsbezogener Probleme algorithmisch effizient gelöst werden kann, d. h. ob die Zeitkomplexität dieser Probleme sich im Verhältnis zur Länge der Eingabe polynomial verhält (siehe 4.).

Erstmals wurde die P=NP-Frage 1971 von Stephen Cook und Leonid Levin gestellt - und seitdem sind außergewöhnliche Forschungsanstrengungen unternommen worden, um dieses Problem zu lösen. Das Besondere hierbei ist, dass zum einen schon Tausende von Forschern aus völlig verschiedenen Gebieten von der Soziologie über die Ingenieurwissenschaften und die Biologie bis zur Energieforschung sich mit dieser Fragestellung beschäftigt haben, andererseits die zugrunde liegende Thematik sehr einfach und intuitiv vermittelbar ist. Wir sind der Auffassung, dass die P=NP-Frage mit all ihren Facetten so wichtig ist, dass sie schulisches
Allgemeingut sein sollte. Mit diesem Beitrag wollen wir versuchen, die elementare Faszination, die von sicherlich einer der bedeutendsten wissenschaftlichen Fragestellungen der Informatik ausgehen kann, an einem einfachen und wichtigen Problem herauszuarbeiten.

 


1. Eigenschaften von Problemklassen history menue scroll up

Lassen wir y gleich der Anzahl der zur Lösung des Problems mit dem gefundenen Algorithmus notwendigen Elementaroperationen sein, dann verhält sich die Anzahl n der gegebenen Elemente im günstigsten Falle y = n. Das ist allerdings niemals in der Praxis der Fall - ja es sieht schon gut aus, wenn gilt y = x n. Nun gilt aber für die weitaus größte Klasse von informatischen Problemen y = x n² oder gar y = x n³. Und Extreme verhalten sich wie y = x 2n, wie y = x 3n.

das Cliquenproblem

das Dominoproblem

das Halteproblem

das K-Farben-Problem

das Rucksackprolem (Knapsackproblem)

das Rundreiseproblem - aber: beachte die Mächtigkeit!

The Busy Beaver-Problem

Greedy Algorithm

das Knotenüberdeckungsproblem

das Teilsummensummenproblem

   
Lösungsverfahren Graphentheorie in der Anwendung - Laufzeitoptimierung und Zeitkomplexität

das ist Komplexität

die Zusammenhänge zwischen den Faktoren

die Zusammenhänge zwischen den Faktoren

die Komplexität eines Problems & Komplexitätsklassen

   
 


2. Lösbarkeit von Problemen - Entscheidbarkeitskriterien history menue scroll up

Lösbar ist eine Aufgabe nur, wenn es ein irgendwie sinnvolles Antwortzeitverhalten auf eine sinnvolle Datenmenge mit eindeutigen (als zum Beispiel schon mal nicht gerundeten) Zwischenergebnissen gibt, deren Aufwand sich im Sinne der Problemstellung
 


3. Entscheidbarkeit history menue scroll up

Entscheidbar ist ein Problem hinsichtlich seiner Lösung, wenn die Anzahl der Zwischenargumente zwar groß, im Extremfall auch sehr groß - aber endlich ist. Ist dies nicht mehr gegeben, so ist auch das Problem hinsichtlich seiner Lösung und/oder seines Lösungsumfanges nicht mehr entscheidbar
Backtracking


4. NP-vollständige Probleme history menue scroll up

Hiermit soll die Aussage getroffen werden, ob ein Algorithmus in endlicher Zeit zum Halten und damit zu einer sinnvollen Menge definierter Ergebnisse kommt oder aber auch nicht! Alle Aufgaben und/oder Algorithmen, welche dies nicht grundsätzlich bejahen, fallen in die Menge der nicht entscheidbaren bzw. nicht lösbaren Probleme - und dies grundsätzlich.
Der folgende Baum zeigt Karps 21 Probleme, inklusive der zugehörigen Reduktion, die er nutzte, um ihre NP-Vollständigkeit nachzuweisen. Zum Beispiel wurde die NP-Vollständigkeit des Rucksackproblems gezeigt, indem das Problem der exakten Überdeckung darauf reduziert wurde.


5. NP-schwierige Probleme history menue scroll up

Die Klasse der NP-vollständigen ist die komplexeste aller Problemklassen. Nicht das es immer ihre Kompliziertheit innerhalb des Algorithmus darstellt - nein, die schiere Menge an zu untersuchenden Fällen kann dazu führen, dass diese Probleme praktisch nicht mehr lösbar sind und nach Alternativen gesucht werden muss.

das Halteproblem

das Cliquenproblem

das K-Farben-Problem

das Rucksackprolem (Knapsackproblem)

das Rundreiseproblem - aber: beachte die Mächtigkeit!

das Hamiltonproblem

das Knotenüberdeckungsproblem

die Türme von Hanoi - mit hoher Anzahl von Scheiben wird das Problem praktisch nicht lösbar - 64 ist bereits enorm hoch

das Post'sche Korrespondenz-Problem

das Teilsummensummenproblem

   
Turing-Maschine


6. Verwandte Themen history menue scroll up

Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.

Worst-Case-Denken

Algorithmentheorie

Komplexität, Mächtigkeit und Aufwand

Praktische Elementaralgorithmen

Klassische algorithmisch lösbare Probleme

Zufall und Computer

Graphentheorie

Petri-Netze

 

Informationsbegriff

Logo für die Signale

Nachrichten

Wissen

Systembegriff

Modellbegriff

Simulation

Denken und Sprache

Zahlen, Daten und Datentypen

Gegenläufigkeit und Verklemmung

Pattern-Matching

 

Funktionen & Prozeduren mit Parameterübergabe

Rekursion

 



zur Hauptseite
© Samuel-von-Pufendorf-Gymnasium Flöha © Frank Rost am 25. Januar 2008

... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehmen ;-)

„Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“

Diddi Hallervorden, dt. Komiker und Kabarettist