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.
Proof complexity investigates how difficult is to prove family of tautologies in propositional proof systems. It plays for the study of feasible proofs the same role that circuit complexity plays for the study of feasible computations. Main problems and motivations in proof complexity are strictly related with problems in complexity theory like NP vs co-NP. In the tutorial we will give an introduction to the field of proof complexity. Then we will show some of the main techniques and results for studying the limits to the provability in one of the most studied proof systems: Resolution. We then will look at stronger proof systems motivating recent problems and results starting from what seen for Resolution. Presentation: Introduction to Circuit Complexity Presentation: Resolution Presentation: Exponential Lower Bounds for DAG-like Resolution Presentation: Other Measures and Methods for Resolution
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