|
Gerlinde Steinhoff

Oberseminar Geometrie, Topologie und Gruppentheorie: Guntram Hainke (Münster): Cech-Kohomologie und Komplexitätstheorie

Thursday, 11.11.2010 10:00 im Raum SR 1d

Mathematik und Informatik

"Ob sich in einer Liste von Zahlen zwei gleiche Zahlen befinden, kann man feststellen, indem man die Liste sortiert. Aber gibt es nicht noch ein schnelleres Verfahren? Ein überraschendes Ergebnis von Steele-Yao (1984) besagt, dass es nicht schneller geht. Noch überraschender vielleicht ist der Beweis, der wesentlich auf einem Resultat von Milnor-Thom (1964) über die Cech-Kohomologie von reellen semialgebraischen Varietäten beruht. In diesem Vortrag diskutieren wir diese beiden Resultate und setzen sie mit dem Begriff des natürlichen Beweises im Sinne von Razborov-Rudich (1994) in Verbindung."



Angelegt am Tuesday, 26.10.2010 13:55 von Gerlinde Steinhoff
Geändert am Wednesday, 03.11.2010 12:00 von Gerlinde Steinhoff
[Edit | Vorlage]

Oberseminare und sonstige Vorträge