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==
===Klasse P===
===Klasse NP===

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

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

==Stephen A. Cook==
===Zur Person Cook===
===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