Self study materials for computational complexity theory

Question

I will be taking a computational complexity theory course in about a year, and as the reference material will be Computational Complexity A Modern Approach I am more than confident that without a proper preparation that course will eat me alive. The book seems to have excellent practise problems in the sense that it will build up my CS toolbox. But I am going to need extra material to help me to get to a level where I can confidently self study the book in quetion. Therefore I was wondering that does there exist a solution manual for the book or are conference papers my only option to check how the quality of my proofs/work as a hint when I am stuck?

Answer 1

To self-study from Computational Complexity: A Modern Approach, the prerequisites are:

• A few courses in algorithms* (you should be comfortable reading and writing pseudocode, using Big-$\mathcal O$ notation, and using abstract data structures like lists, sets and hashmaps)
• A course in discrete math
• A course which treats Finite State Machines and formal languages** (To the point where you are comfortable drawing and reading finite state machines)
• Any course which teaches proofs

Most Bachelor (undergraduate) courses teach all the above. I recommend at least $3$ of the above; the book is written well enough that it remains quite accessible. It does not assume any prior knowledge about complexity classes or Turing Machines.

If you wish to prepare well for a particular course a year in advance, then find out which chapters the course discusses, and read those and then some more, including some exercises (a single-semester course can probably cover less than half the book). Ask the professor which chapters are used, as this changes from one year to the next (Be prepared that the professor has not decided this a year in advance, because she will decide based on what works this year. If she does give an answer, don't treat it as binding or unchanging).

When these requirements are met, my experience is that a big obstacle to overcome is that some students from a CS background have a ``coding mindset" in which, when presented with a problem, they try to solve it with an algorithm. That is not the objective here. Instead, the objective is to understand how different problems relate to each other, and to understand what is the computational power different computational models (e.g. Turing Machines, polynomial-size circuits, FSMs, Turing Machines which use a polynomial amount of memory. And what if they are allowed to flip random coins?). We wish to understand how these two things - problems and computational models - map onto each other. Inevitably, this means proving statements of the form "This problem is too difficult to be solved by that computational model", and "This computational model is more powerful than that one'', and you can't program your way out of that. This is more similar in flavour to abstract algebra, in which one simply tries to comprehend all the groups and rings that are out there; you compare their properties, without trying to code up the multiplication for a particular group.

If you have more time, then read Quantum Computing Since Democritus by Scott Aaronson, because (it is a fun read and) it motivates the questions that are asked in complexity theory.

If you have infinite time, then you can program a SAT Solver; this will help you get familiar with Boolean formulas.

*For example, The Design and Analysis of Algorithms, by Anany Levitin.

**I learned from and recommend Introduction to Languages and the Theory of Computation, by John Martin. It goes all the way from Finite State Machines to Turing Machines. Any book on formal languages should suffice.