P-NP-Problem SS10

Autoren:

1. Ragna-Diana Steglich (sirasteg@stud.hs-zigr.de)
2. Elisabeth Vogel (sielvoge@stud.hs-zigr.de)

Motivation

Komplexitätsklassen

In den meisten Fällen ist es sehr schwierig zu entscheiden, ob ein Problem einfach oder nur sehr schwer lösbar ist. Es ist zum Beispiel ohne weiteres möglich, dass Probleme, die sich formulierungstechnisch nur sehr gering unterscheiden, vollkommen unterschiedliche Aufwände zu ihrer Lösung verlangen. Die folgende Tabelle kann dies verdeutlichen:

Für das P-NP-Problem ist es von Vorteil die Komplexitätsklassen \mathcal{P},\mathcal{NP}, und \mathcal{EXPTIME} genauer zu untersuchen, wobei \mathcal{P} und \mathcal{NP} im Vordergrund stehen werden. Die Probleme, die mehr oder weniger leicht und informell effizient lösbar sind, schreibt man der Komplexitätsklasse \mathcal{P} zu. \mathcal{NP} definiert die Probleme, für die eine Lösung in polynomialer Zeit einfach zu verfizieren ist. Ferner kann die Klasse \mathcal{EXPTIME} als eine Art "Überklasse" bezeichnet werden, denn es gilt \mathcal{P<EXPTIME}. Leider ist aber noch unbekannt ob NP<exptime oder np="EXPTIME" ist. untereinander verhalten sich die komplexit p und undurchsichtig denn es ist noch nicht gekl ob gilt wobei nur wenigsten forscher an glauben. folgende grafik illustriert m verbindung der klassen untereinander:><h3 id="Klasse_P">Klasse P</h3><h3 id="Klasse_NP">Klasse NP</h3><h2 id="Reduktion">Reduktion</h2><h3 id="Polynomiale_Reduktion">Polynomiale Reduktion</h3><h2 id="NP-Vollständigkeit">NP-Vollständigkeit</h2><h3 id="NP-schwere_Probleme">NP-schwere Probleme</h3><h3 id="NP-vollständige_Probleme">NP-vollständige Probleme</h3><h2 id="Stephen_A._Cook">Stephen A. Cook</h2><h3 id="Zur_Person_Cook">Zur Person Cook</h3><h3 id="Satz_von_COOK">Satz von COOK</h3><h3 id="CLIQUEN-Problem">CLIQUEN-Problem</h3><h2 id="NP-Vollständigkeitsbeweis">NP-Vollständigkeitsbeweis</h2><h2 id="Praktische_Unlösbarkeit">Praktische Unlösbarkeit</h2><h2 id="Frank_P._Ramsey">Frank P. Ramsey</h2><h3 id="Zur_Person_Ramsey">Zur Person Ramsey</h3><h3 id="RAMSEY-Problem">RAMSEY-Problem</h3><h2 id="Pseudopolynomiale_Algorithmen">Pseudopolynomiale Algorithmen</h2><h2 id="Übungsaufgaben">Übungsaufgaben</h2><h2 id="Quellen">Quellen</h2><h3 id="Literatur">Literatur</h3><dl><dt>[1] Christian Wagenknecht</dt><dd>Algorithmen und Komplexität.- Fachbuchverlag Leipzig, 2003.- ISBN 3-446-22314-2</dd><dt>[2] Robert Sedgewick</dt><dd>Algorithmen, 3. unveränderte Auflage - Addison-Wesley, 1994 - ISBN 3-89319-402-9</dd></dl><h3 id="Weblinks">Weblinks</h3><dl><dt>[1] http</dt><dd>//de.wikipedia.org/wiki/P-NP-Problem</dd><dt>[2] http</dt><dd>//de.wikipedia.org/wiki/Komplexit%C3%A4tsklasse</dd><dt>[3] http</dt><dd>//de.wikipedia.org/wiki/Komplexit%C3%A4tstheorie</dd><dt>[4] http</dt><dd>//de.wikipedia.org/wiki/Liste_von_Komplexit%C3%A4tsklassen</dd><dt>[5] http</dt><dd>//de.wikipedia.org/wiki/Stephen_A._Cook</dd><dt>[6] http</dt><dd>//de.wikipedia.org/wiki/Frank_Plumpton_Ramsey</dd><dt>[7] http</dt><dd>//de.wikipedia.org/wiki/Millennium-Probleme</dd><dt>[8] http</dt><dd>//www.uni-protokolle.de/Lexikon/P/NP-Problem.html</dd><dt>[9] http</dt><dd>//www.informatik.uni-bremen.de/theorie/teach/lehre/thi2/2007/Folien/0406.pdf</dd></dl><p><br></p><h2 id="Siehe_auch">Siehe auch</h2><dl><dt>[1] Hompage von Stephen A. Cook</dt><dd>http://www.cs.toronto.edu/~sacook/</dd><dt>[2] Clay Mathematics Institute</dt><dd>http://www.claymath.org/millennium/</dd><dt>[3] MacTutor History of Mathematics archive</dt><dd>http://www-history.mcs.st-andrews.ac.uk/Biographies/Ramsey.html</dd></dl></exptime>