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===

==Steven 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===
===Weblinks===

==Siehe auch==