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.

Licensed to the public under https://creativecommons.org/licenses/by/4.0/

about this event: https://cfp.gulas.ch/gpn23/talk/8JMXKU/