Seminar Einführung in die Algorithmik: Algorithmen in der Aussagenlogik

Dies ist das Bachelorseminar mit dem Titel Algorithmik: Algorithmen in der Aussagenlogik.

Thematisch ist dieses Seminar gleich mit dem Seminar Algorithmik Beweiskomplexität. Dort finden sich ebenfalls die Informationen für die Bachelorstudierenden.

In diesem Bachelorseminar wollen wir sehr einfache Aspekte des Themenbereichs Beweiskomplexität zu Algorithmen in der Aussagenlogik kennelernen und einige grundlegende Paper verstehen.

Darum geht es inhaltlich:

In Proof Complexity, one tries to understand and analyze the computational resources required to prove or refute logical statements. More intuitively, one is interested in studying how to give short (and efficiently verifiable) proofs of the fact that a given CNF formula is unsatisfiable. The resolution calculus is one method how one can show unsatisfiability. This course will primarily focus on resolution as a proof system. Proof Complexity has not only a deep connection to the P vs. NP problem but also many exciting interrelations to the applied field of SAT Solving.