# Computation Complexity books for a mathematician

I recently attented to some computational complexity talks (or complexity theory, I am not sure which is the correct name) and I fell in love with it. I would like to find some books, online courses... in general resources of any kind to self-study this (securely) wonderfull subject.

My backgrund is pure mathematics with emphasys in discrete mathematics (graph theorey, crypto, coding thoery, combinatorics...), with no background in computer science. I am not sure if the last one is mandatory.

• Seeing the other answers now, I feel like this question is best answered with a community wiki answer. If @Discretelizard and Mars agree that I incorporate their recommendations into my answer, I'll make it a wiki and update. – Pål GD Jun 18 '20 at 16:51
• @PålGD For me that would be perfect! I will check them all and see what I like most! – Bean Guy Jun 18 '20 at 21:19
• Shouldn't this question be on the CS Theory site? – einpoklum Jun 19 '20 at 14:48
• @einpoklum no, cstheory is for computer scientists and researchers in related fields. This is not a research related question. But I do admit that we have very overlapping interests. – Pål GD Jun 19 '20 at 20:50
• I don't know about the community wiki, @PålGD, but that is fine with me. – Mars Jun 20 '20 at 3:53

Michael Sipser's text book Introduction to the Theory of Computation is a classic introduction to computation theory, and gives an introduction to complexity theory in the end.

PART 1: AUTOMATA AND LANGUAGES.
1. Regular Languages.
2. Context-Free Languages.

PART 2: COMPUTABILITY THEORY.
3. The Church-Turing Thesis.
4. Decidability.
5. Reducibility.
6. Advanced Topics in Computability Theory.

PART 3: COMPLEXITY THEORY.
7. Time Complexity.
8. Space Complexity.
9. Intractability.
10. Advanced Topics in Complexity Theory.

• I suppose that the difference between Computability and Complexity is that, in the first one cares about if a problem is computable or not, and in the second one, one cares about the efficiency of such a computable problems. Am I right, more or less? – Bean Guy Jun 18 '20 at 13:38
• I would say that computability deals with the fundamental properties of (mainly) Turing machines and other automata. Complexity theory typically deals with more fine-grained analysis of machines. Be aware that you need to know some computation theory in order to understand complexity theory. – Pål GD Jun 18 '20 at 14:04
• +1; Sipser was my first thought on seeing the HNQ title. (It's one of the very few textbooks I found I was able to learn from just by reading the book and following the exercises.) – chrylis -cautiouslyoptimistic- Jun 19 '20 at 1:01
• @BeanGuy Yes you are right, more or less. – 6005 Jun 19 '20 at 12:00

You might want to consider Computational Complexity: A Modern Approach by Arora and Barak. Roughly speaking, its early chapters overlap with later chapters in Sipser, and it has more material on computational complexity per se.

Arora and Barak's book (A&B) seems self-contained. For example, you don't need to know the parts of Sipser or similar books that A&B don't cover, in order to understand A&B. On the other hand, my sense is that A&B moves a little bit more quickly and requires a little bit more insight than Sipser. I could be wrong. I am reading A&B and have only glanced at parts of Sipser and have read a few comments online comparing the two.

In terms of content, my guess is that A&B is one good option for your interests, and if the level of A&B is inappropriate for you, it will be because it is too easy (it's not, for me), and because some other book goes into ideas more deeply more quickly.

• It's self-contained because it's a million pages long... – einpoklum Jun 19 '20 at 14:46
• I suppose that true self-containment would require a much longer book, with at least a countably infinite number of pages. – Mars Jun 20 '20 at 3:47

I can recommend the book Computational Complexity Theory, edited by Steven Rudich and Avi Wigderson, which is based on a graduate summer school by the IAS/Park city mathematics institute, with lectures by various experts in the field.

The purpose of this book is to provide the basics, some history and a glimpse into the research in some areas of computational complexity theory, aimed at mathematics students.

As such, this book is not a replacement for an introductory book such as Sisper's, but can be read independently to get a feeling what some sub-fields of complexity theory look like, and can help to guide a future focus.

Week One:
COMPLEXITY THEORY: FROM GÖDEL TO FEYNMAN

Steven Rudich, Complexity Theory: from Gödel to Feynmann
Avi Wigderson, Average case Complexity
Sanjeev Arora, Exploring Complexity through Reductions
Ran Raz, Quantum Computation

Week Two:
LOWER BOUNDS

Ran Raz, Circuit and Communication Complexity
Paul Beame, Proof Complexity

Week Three:
RANDOMNESS IN COMPUTATION

Oded Goldreich, Pseudorandomness - Part I
Luca Trevisan, Pseudorandomness - Part II