Vortragsankündigung, Bereichsseminar Theoretische Informatik,
Dienstag, den 7. 11. 2000, 15:15 - 16:45, Hauptgebäude Raum 3-68
Heiko Stamer und Johannes Waldmann, Institut für Informatik, Universität Leipzig

Neuigkeiten vom Postschen Korrespondenz-Problem

Das Postsche Korrespondenzproblem (PCP) besteht darin, zu entscheiden, ob zwei gegebene Morphismen für irgendein nichtleeres Wort übereinstimmen.

Beispiel: für die Morphismen g, h von {A,B,C}* nach {0,1}* gegeben durch die Tabelle

A B C
g 110 0 1
h 1 1 01

finden wir die Lösung AACBCCBC wegen g(AACBCCBC) = 110110101101 = h (AACBCCBC).

Obwohl das PCP einfach aussieht, ist es algorithmisch sehr schwer (d. h. nicht rekursiv entscheidbar).

Wir haben sowohl theoretisch als auch praktisch einige Teilklassen von PCPs (mit kleinem Quell- und Ziel-Alphabet) untersucht, um einerseits dafür Entscheidbarkeitsresultate zu erhalten oder zu verbessern und andererseits interessante Beispiele für die Grundvorlesung über Berechenbarkeit herzustellen.

Dabei suchen wir, in Analogie zu Busy-Beaver-Turingmaschinen, nach kleinen lösbaren PCPs, deren kürzeste Lösung jedoch sehr lang ist. Beispiel: finde die kleinste Lösung von

A B C
g 1 10 1101
h 0 1011 1

Im Vortrag stellen wir die benutzten Suchverfahren, Ergebnisse und offenen Fragen vor, und eröffnen damit auch einen Wettbewerb. Es winken Preise! Details geben wir dann auf einer Web-Seite bekannt.

Der Vortrag richtet sich an einen breiten Interessentenkreis und setzt keine besonderen Kenntnisse in Theoretischer Informatik voraus.

http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de