|
|
|
 |
Lehrstuhl
Mathematik & Informatik
Seminar zum P-NP Problem SS 04 |
|
| |
| |
|
 |
|
|
| LV-NR |
150 409
|
| Veranstaltung |
Seminar zum P-NP Problem
|
| Dozent(inn)en |
Simon, H. U.
|
| |
|
| |
|
Vorraussetzungen |
| |
|
Das Seminar ist die ideale Ergänzung zur im selben Semester angebotenen
Komplexitätstheorie-Vorlesung.
Elementare Grundkenntnisse zu der Thematik, wie sie etwa im Theorieteil der Vorlesung "Einführung in die
Informatik'' oder im komplexitätstheoretischen Teil der Vorlesung "Theoretische Informatik'' vermittelt werden,
werden weitgehend vorausgesetzt. (Diese Voraussetzungen sind aber von mathematisch gebildeten Studierenden
relativ rasch im Selbststudium herstellbar.)
|
| |
|
Kommentar |
| |
|
Die Frage, ob jede von einer nicht-deterministischen Turing-Maschine in Polynomialzeit erkennbare Sprache auch
von einer deterministischen Turing-Maschine in Polynomialzeit erkannt werden kann, wird als das P-NP Problem
bezeichnet. Es gilt als das zentrale offene Problem der Informatik und hat inzwischen auch das Interesse der
mathematischen Forscher und Forscherinnen gefunden. (Es ist zum Beispiel das erste "Millenium Prize Problem''
auf der Liste des "Clay Mathematics Institute"). Im Seminar werden wir anhand von
Original- und "Übersichtsarbeiten den derzeitigen Wissensstand zu diesem Problem aufarbeiten. Besonders intensiv
werden wir uns mit der Forschungsrichtung befassen, die sich dem P-NP Problem über die Analyse der sogenannten
"Beweiskomplexität'' annähert.
Anmeldung beim Prof. Simon oder Frau
Weissmann.
|
| |
|
Literatur |
| |
|
Original- und Übersichtsarbeiten, die bei der Vorbesprechung verteilt werden.
Demjenigen der sich einen Überblick verschaffen möchte seien folgende Artikel empfohlen:
http://citeseer.nj.nec.com/sipser92history.html
http://citeseer.nj.nec.com/316852.html
|
| |
|
Zeitplan |
| |
|
| 07.6.2004 |
Komplexitaet aussagenlogischer Beweise I
|
Thorsten Doliwa
Michael Kallweit
|
| 14.6.2004 |
Komplexitaet aussagenlogischer Beweise II
|
Thorsten Doliwa
Michael Kallweit
|
| 05.7.2004 |
Heuristiken fuer semizufaellige Graphenprobleme I
|
Martina Berezhna
Martin Ficker
Ralf Nowithnig
|
| 19.7.2004 |
Heuristiken fuer semizufaellige Graphenprobleme II
|
Martina Berezhna
Martin Ficker
Ralf Nowithnig
|
| 26.7.2004 |
Heuristiken fuer semizufaellige Graphenprobleme III
|
Martina Berezhna
Martin Ficker
Ralf Nowithnig
|
|
|
| |
|
|
