01.09, 18:00–19:30 (Europe/Berlin), B002 - Höhle der Hohlerde
Language: Deutsch
Wie uns ein Blick in parallele Welten, in denen es bestimmte Orakel gibt, beweist, dass die P-NP-Frage schwer zu beantworten ist: es bräuchte einen Beweis, der sich nicht in Alternativrealitäten übertragen lässt.
Ich stelle einen interessanten Beweis aus der theoretischen Informatik vor, genauer Komplexitätstheorie: wir beweisen, dass es schwer ist, zu zeigen, ob P=NP oder P≠NP.
Inhalt:
* Kurze Einführung grundlegender Begriffe (Algorithmus, Berechnung, P, NP)
* Orakelmaschinen
* Orakelkonstruktion für P=NP
* Orakelkonstruktion für P≠NP
Geeignet für Theorie-Interessierte und mathematisch veranlagte Personen. Eine gewisse Vertrautheit mit den Arbeitsmethoden der theoretischen Informatik ist empfehlenswert, um gut mitzukommen.
Die Freuden der theoretischen Informatik sind unerschöpflich
Begeistert für Fahrkarten und Theoretische Informatik.