MRMCD 2023

Parallelwelten der Theoretischen Informatik
09-01, 18:00–19:30 (Europe/Berlin), B002 - Cave of the hollow earth
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.