19.06.2025 –, ZKM Vortragssaal
Sprache: Deutsch
Interessante Probleme sind in der Regel nicht leicht zu lösen. Die Komplexitätstheorie der theoretischen Informatik hilft uns diese Probleme zu erkennen und zu beantworten mit welchen Sprachen, Methoden und Datendarstellungen wir diese lösen und abbilden können.
Die wichtigste Kategorie interessanter Probleme sind mindestens NP-schwer und lassen auf die Erfüllbarkeit logischer Gleichungen (SAT) zurückzuführen. Erstaunlicherweise lassen sich diese auf die Erfüllbarkeit von Gruppen von minimal drei Variablen (3-SAT) reduzieren, nicht jedoch- nach aktuellem Stand- auf Gruppen mit nur zwei Variablen (2-SAT). Ebenso fällt die Erstellung von Zeitplänen in diese Klasse, wenn Vortragende mehr als zwei Vorträge halten. Dieses versteckte Muster kann uns erklären, warum Key-Value-Stores zwar sehr effizient sind, wir zum Speichern unseres Wissens doch nicht darauf verzichten können, mindestens auf Triplet-Stores oder allgemeinere relationale Datenbanken setzen zu müssen.
Mit dem NKC Z80 in die Computerwelt gekommen, habe Mathe studiert und unterrichte nun Informatik.
* Frühere Talks auf media.ccc.de
* Podcasts zur GPN