[updated on 2014.07.08]
Instructor: Phokion G. Kolaitis (University of California Santa Cruz & IBM Research – Almaden)
Title: Logic and Computation
Final versions – slides:
A Short Description:
The aim of this course is to highlight the interaction between logic and computation with emphasis on the connections between logic and computational complexity, as well as on some of the uses of logic in databases. Topics to be covered include:
1. Propositional Logic and Computational Complexity: The satisfiability problem and its variants; tractable cases of the satisfiability problem; Schaefer’s Dichotomy Theorem for the computational complexity of generalized satisfiability problems.
2. First-Order Logic: Computational aspects of first-order logic on finite structures; first-order logic as a database query language; first-order logic and database dependencies; limitations of the expressive power of first-order logic on finite structures; Ehrenfeucht-Fraïssé games.
3. Extensions of First-Order Logic: Datalog and Least Fixed-Point Logic; Existential Second-Order Logic; descriptive computational complexity.