AuK/P-NP-Problem SS10

Wiki-Quelltext dieser Seite.

'''Autoren:'''

#Ragna-Diana Steglich    ([mailto:sirasteg@stud.hs-zigr.de sirasteg@stud.hs-zigr.de])
#Elisabeth Vogel      ([mailto:sielvoge@stud.hs-zigr.de 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:

[[Bild:Vergleich.PNG]] 

Für das P-NP-Problem ist es von Vorteil die Komplexitätsklassen <math> \mathcal{P},\mathcal{NP},</math> und <math> \mathcal{EXPTIME}</math> genauer zu untersuchen, wobei <math> \mathcal{P}</math> und <math> \mathcal{NP}</math> im Vordergrund stehen werden. 
Die Probleme, die mehr oder weniger leicht und informell effizient lösbar sind, schreibt man der Komplexitätsklasse <math> \mathcal{P}</math> zu. <math> \mathcal{NP}</math> definiert die Probleme, für die eine Lösung in polynomialer Zeit einfach zu verfizieren ist. Ferner kann die Klasse <math> \mathcal{EXPTIME}</math> als eine Art "Überklasse" bezeichnet werden, denn es gilt  <math>\mathcal{P} \subset \mathcal{EXPTIME}</math>. Leider ist aber noch unbekannt ob <math>\mathcal{NP} \subset \mathcal{EXPTIME}</math> oder <math>\mathcal{NP} = \mathcal{EXPTIME}</math> ist. Untereinander verhalten sich die Komplexitätsklassen <math> \mathcal{P}</math> und <math> \mathcal{NP}</math> ähnlich undurchsichtig, denn es ist noch nicht geklärt, ob <math>\mathcal{P} ={NP}</math> oder <math>\mathcal{P} \subset \mathcal{NP}</math> gilt, wobei nur die wenigsten Forscher an <math>\mathcal{P} ={NP}</math> glauben. Die folgende Grafik illustriert die mögliche Verbindung der Klassen untereinander:

===Klasse P===

;Definition
:<math> \mathcal{P}</math> ist die Klasse aller Probleme, die mit deterministischen Algorithmen in polynomialer Zeit gelöst werden können.


Der Klasse <math> \mathcal{P}</math>, manchmal findet sich auch die Bezeichnung <math> \mathcal{PTIME}</math>, werden also Probleme der Größe <math> \mathcal{n}</math> (Eingabewort) zugeordnet, für deren Lösung der Aufwand im worst-case durch ein Polynom in <math> \mathcal{n}</math> nach oben beschränkt werden kann. Das Polynom besitzt dann dann die Größe der Eingabe. Abstrakter gesagt umfasst die Klasse <math> \mathcal{P}</math> Entscheidungsprobleme die in Polynomzeit für deterministische TURING-Maschinen lösbar sind. Allgemein wird diese Komplexitätsklasse auch als Klasse der "praktisch lösbaren" Probleme betrachtet. 
Algorithmen, deren Komplexität nicht durch Polynome beschränkt werden können sind ineffizient, das heißt, dass der Aufwand mit der Anzahl der Eingaben exponentiell nach oben steigt. Daraus ergibt sich die unumgängliche Tatsache, dass diese Algorithmen die Rechenkapazität jedes irdischen Computers irgendwann bei weitem sprengen würden. 

===Klasse NP===

==Reduktion==
===Polynomiale Reduktion===

==NP-Vollständigkeit==
===NP-schwere Probleme===
===NP-vollständige Probleme===

==Stephen A. Cook==
===Zur Person Cook===
Einer der bedeutesten Professoren der Informatik ist Steven Arthur Cook. Er wurde am 14.Dezember 1939 in Buffalo, New York geboren und lebt heute in Kanada, wo er an der University of Toronto unterrichtet. Die größte Aufmerksamkeit widmete er der Komplexitätstheorie, in der er 1971 mit dem ‚Satz von Cook‘ berühmt wurde und 1982 den Turing Award erhielt, welcher an Personen verliehen wird, die besonders zur Entwicklung der Informatik beigetragen haben.

===Satz von COOK===
===CLIQUEN-Problem===

==NP-Vollständigkeitsbeweis==

==Praktische Unlösbarkeit==

==Frank P. Ramsey==
===Zur Person Ramsey===
===RAMSEY-Problem===

==Pseudopolynomiale Algorithmen==

==Übungsaufgaben==

==Quellen==
===Literatur===
; [1] Christian Wagenknecht
: Algorithmen und Komplexität.- Fachbuchverlag Leipzig, 2003.- ISBN 3-446-22314-2
; [2] Robert Sedgewick
: Algorithmen, 3. unveränderte Auflage - Addison-Wesley, 1994 - ISBN 3-89319-402-9
===Weblinks===
; [1] http://de.wikipedia.org/wiki/P-NP-Problem
; [2] http://de.wikipedia.org/wiki/Komplexit%C3%A4tsklasse
; [3] http://de.wikipedia.org/wiki/Komplexit%C3%A4tstheorie
; [4] http://de.wikipedia.org/wiki/Liste_von_Komplexit%C3%A4tsklassen
; [5] http://de.wikipedia.org/wiki/Stephen_A._Cook
; [6] http://de.wikipedia.org/wiki/Frank_Plumpton_Ramsey
; [7] http://de.wikipedia.org/wiki/Millennium-Probleme
; [8] http://www.uni-protokolle.de/Lexikon/P/NP-Problem.html
; [9] http://www.informatik.uni-bremen.de/theorie/teach/lehre/thi2/2007/Folien/0406.pdf


==Siehe auch==
; [1] Hompage von Stephen A. Cook
: http://www.cs.toronto.edu/~sacook/
; [2] Clay Mathematics Institute
: http://www.claymath.org/millennium/
; [3] MacTutor History of Mathematics archive
: http://www-history.mcs.st-andrews.ac.uk/Biographies/Ramsey.html