# Self study materials for computational complexity theory

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?

• This question is not about Computer Science (the website), but teaching/learning CS, so it is in principle on topic. I'm not sure if your question fits the Q&A format well, though. Is it really worked-out answers in particular you are looking for, or would any other preparation for this material do? If the latter, do the answers to this question or that question answer your question? – Discrete lizard Sep 28 '20 at 11:03
• Can you specify what prior knowledge you now posses? e.g., are you a Mathematics student; do you have a BSc. in CS; have you taken any programming classes? – Lieuwe Vinkhuijzen Sep 28 '20 at 14:14
• @Discretelizard In principle I think that any material that happens to discuss the problems and provide any level of reference with regards to the proofs is sufficient. This might be uneducated conclusion, but I do not think that the links you posted answer the question. Namely, TCS acts and feels so different from other mathematics I have encountered, so I am looking for material that really helps me to ingrain the way of thinking and constructing the proofs. – Qwaster Sep 28 '20 at 16:01
• @LieuweVinkhuijzen I am currently in my last year of computer science BSc. All my electives have been/are in mathematics/computer science; abstract algebra, linear algebra, stochastics, advanced algorithms etc. All-in-all a versatile package. I have taken a bachelor level theoretical computer science course, so I have the at most basics needed to read the material. However if analysis is in any way relevant I am in trouble. Besides mandatory calc. courses, I do not have any knowledge in analysis. – Qwaster Sep 28 '20 at 16:07
• @Qwaster I think the most relevant information you could give here would be whether you've had a "serious" proof-based mathematics course. The specific topic doesn't matter much, analysis for example would have been fine even though it usually doesn't have many direct applications in most topics within TCS. While there definitely are a few tricks in TCS that are specific to the field, it is often more important to have good experience with making proofs in general, the so-called "mathematical maturity". If you don't feel confident with proofs, work on that. Otherwise, I think you'll be fine. – Discrete lizard Sep 28 '20 at 16:36

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.

• Modern American-style complexity theory doesn't really rely on finite state machines other than Turing machines, apart from the complexity class LogCFL. – Yuval Filmus Sep 28 '20 at 21:23
• That's true, but TMs are the topic of six of the first seven chapters of this book. Without this background, the TM is a lot of stuff all at once, and this book doesn't spend as much time as the book Introduction to Languages and the Theory of Computation, for example, on getting students familiar with designing FSMs and TMs. It does spend some pages on this, true, and it is probably possible to skip this background, but I added it because I feel a student will be at a significant advantage. Nevertheless, on an hour-by-hour basis, it may be more useful to just read A&B twice than study FSM. – Lieuwe Vinkhuijzen Sep 29 '20 at 7:29