Prädikatenlogik und Datenbanken (2)

Wir wollen noch zeigen, dass das Auswertungsproblem der Prädikatenlogik (und damit auch die Anfragebeantwortung in Datenbanken) PSpace-vollständig sind, was man leicht durch Reduktion von TrueQBF zeigen kann. Zum Schluss schauen wir noch einmal auf die Grenzen der Ausdrucksstärke von Prädikatenlogik als Anfragesprache.
► Playliste für diesen Videokurs: • Theoretische Informati...
► Vorlesungsfolien zum Download: iccl.inf.tu-dr... (21. Vorlesung)
► Aktuelle und frühere Versionen der Vorlesung: iccl.inf.tu-dr...
► Fehler gefunden? Issues melden auf github: github.com/kno...