202402121702

Tags : Complexity Theory

Complexity Theory

---

What is this course about?

Complexity classes; classifying problems and comparing hardness The goal is to have efficient algorithms. Understanding the complexity provides us with a sanity check; what can and cannot be solved efficiently, whether or not it makes sense to look for more efficiency etc.

The Church-Turing thesis (all that is computable is computable by a Turing Machine) gives us reason to believe that Turing Machines are the right model of computation. The feasibility thesis (polytime on any model $\sim$ polytime on TMs) gives us reason to decide that ‘polynomial time’ is the right notion of efficiency.

---

Course plan:

1. NP-completeness and proof of Cook-Levin Theorem
2. Time and Space Hierarchy Theorems
3. Alternation, Savitch’s Theorem
4. Structural Complexity
5. Counting Problems
6. Randomness and Complexity
7. Interactive Proofs, Zero-knowledge proofs

---

Notes

• Complexity Theory
• Cook-Levin Theorem ($SAT$ is $NP-$complete.)
• Web of Reductions (Some standard reductions)
• Co-NP (Complexity Class) (and $NP\cap Co-NP$)
• Search vs Decision for NP complete problems
• EXP (Complexity Class)
• Ladner’s Theorem
• Time and Space Hierarchy Theorems
• Savitch’s Theorem
• Quantified Boolean Formulas
• Complete problem for NL
• Immerman–Szelepcsényi Theorem
• Non deterministic Space Hierarchy Theorem
• Polynomial-Time Hierarchy
• Alternating Turing Machine
• Circuit Value Problem
• Karp-Lipton Theorem
• the B something theorem
• Can there be sparse sets that are NP-hard?
• Randomised or Probabilistic Computation

---

MOCs

---

References

• [Sipser]
• [Hopcroft-Ullman]
• [Arora-Barak]
• [Luca Trevisan - UCB]
• [Dieter van Melkebeek - University of Wisconsin]
• [Prahladh Harsha, Ramprasad Saptharishi - TIFR]