Basics of Computational Complexity

ABOUT THE COURSE: We will start this course by mathematically formalizing computation and algorithms. Our approach in the course would be to look at famous concrete problems and prove theorems about their uncomputability, or, if computable, then how fast can they be computationally solved. The problems we will cover in this course are: the halting problem, boolean formula satisfiability (the P!=NP question), quantified boolean formula, formula minimization, polynomial identity testing, undirected graph reachability, permanent and graph isomorphism. While studying these computational problems we will define various complexity classes and develop various tools used in modern complexity theory.INTENDED AUDIENCE: Computer Science & Engineering, Mathematics, Electronics, Physics, & similar disciplines.PREREQUISITES: Preferable (but not necessary)-- Theory of Computation, or Algorithms, or Discrete Mathematics.INDUSTRY SUPPORT: Discrete Optimization, Cryptography/ Cyber Security, Coding theory, Computer Algebra, Symbolic Computing Software, , Learning Software.

Week 1: Formalizing Problems, Machines, Time & Space.Week 2:Computability. Complexity ClassesWeek 3:Nondeterminism. Reduction.Week 4:co-Classes. EXP-classes.Week 5:Hierarchy theorems.Week 6:Oracle. Relativization.Week 7:Space complexity.Week 8:Polynomial hierarchy.Week 9:Counting classes.Week 10:Counting vs Hierarchy.Week 11:Probabilistic TM.Week 12:Interaction & Circuits.