P-NP-Problem SS10

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2010-06-03T10:31:45+00:00. Aktuelle Version

Inhaltsverzeichnis

Autoren:

  1. Ragna-Diana Steglich (sirasteg@stud.hs-zigr.de)
  2. Elisabeth Vogel (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

Siehe auch