P-NP-Problem SS10

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

Stephen 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

[1] Christian Wagenknecht

Algorithmen und Komplexität.- Fachbuchverlag Leipzig, 2003.- ISBN 3-446-22314-2

[2] Robert Sedgewick

Algorithmen, 3. unveränderte Auflage - Addison-Wesley, 1994 - ISBN 3-89319-402-9

Weblinks

[1] http

//de.wikipedia.org/wiki/P-NP-Problem

[2] http

//de.wikipedia.org/wiki/Komplexit%C3%A4tsklasse

[3] http

//de.wikipedia.org/wiki/Komplexit%C3%A4tstheorie

[4] http

//de.wikipedia.org/wiki/Liste_von_Komplexit%C3%A4tsklassen

[5] http

//de.wikipedia.org/wiki/Stephen_A._Cook

[6] http

//de.wikipedia.org/wiki/Frank_Plumpton_Ramsey

[7] http

//de.wikipedia.org/wiki/Millennium-Probleme

[8] http

//www.uni-protokolle.de/Lexikon/P/NP-Problem.html

[9] http

//www.informatik.uni-bremen.de/theorie/teach/lehre/thi2/2007/Folien/0406.pdf

Siehe auch

[1] Hompage von Stephen A. Cook

http://www.cs.toronto.edu/~sacook/

[2] Clay Mathematics Institute

http://www.claymath.org/millennium/

[3] MacTutor History of Mathematics archive

http://www-history.mcs.st-andrews.ac.uk/Biographies/Ramsey.html