P-NP-Problem WS13-14

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2013-11-20T18:03:52+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