We will look at the famous P vs. NP problem and how this question led to the rich development of computational complexity classes. Topics we plan to cover include: the polynomial-time hierarchy and counting complexity, alternation, probabilistic and non-uniform models, interactive and probabilistically checkable proof systems and a structural approach to quantum computing.
Going back to the famous theorem by Cook and Levin, satisfiability problems have turned out to be central in computational complexity theory. In this tutorial we will prove complexity classifications of satisfiability and related problems for propositional logic, modal logic, temporal logic, constraint satisfaction, default logic, etc. In each case we will identify tractable fragments of algorithmic problems that are intractable in the general case. We will develop a powerful toolbox to attack questions like these, making use of Post's lattice of all closed classes of Boolean functions. Presentation: Constraint Satisfaction Presentation: Default Logic Presentation: Linear Temporal Logic Classes
Complexity of Graph Algorithms Based on Matrix Multiplication
We consider ways of harnessing the power of fast algebraic matrix multiplication algorithms to solve various graph algorithmic problems, such as (dynamic) reachability problems, shortest paths problems and matching problems. Presentation: pdf Presentation: pptx