P-NP-Problem WS13-14
Aus ProgrammingWiki
Archivierte Version vom 2013-11-20T18:14:58+00:00. Aktuelle Version
Inhaltsverzeichnis |
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