AuK/P-NP-Problem WS13-14

Wiki-Quelltext dieser Seite.

==Einleitung==
==Die Klassen P und NP==
==NP-Vollständigkeit==
===Polynomiale Reduktion===
===NP-schwere Probleme===
===NP-vollständige Probleme===
===Nachweis der NP-Vollständigkeit eines Problems===
==Satz von Steven A. Cook==
==Vorteile praktischer Unlösbarkeit==
==Das Ramsey-Problem==
==Pseudopolynomiale Algorithmen==
==Übungen==
==Literaturverzeichnis==
* Wagenknecht, Christian: Algorithmen und Komplexität, Fachbuchverlag Leipzig, 2003
* Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford: Algorithmen, eine Einführung,Oldenbourg Verlag, 2007