7
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$
    – Pål GD
    Jun 18, 2020 at 16:51
  • $\begingroup$ @PålGD For me that would be perfect! I will check them all and see what I like most! $\endgroup$
    – Bean Guy
    Jun 18, 2020 at 21:19
  • $\begingroup$ Shouldn't this question be on the CS Theory site? $\endgroup$
    – einpoklum
    Jun 19, 2020 at 14:48
  • $\begingroup$ @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. $\endgroup$
    – Pål GD
    Jun 19, 2020 at 20:50
  • $\begingroup$ I don't know about the community wiki, @PålGD, but that is fine with me. $\endgroup$
    – Mars
    Jun 20, 2020 at 3:53

3 Answers 3

Reset to default
11
$\begingroup$

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.

I don't know how to answer the question better than just providing the table of contents of the book.

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.
Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ 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? $\endgroup$
    – Bean Guy
    Jun 18, 2020 at 13:38
  • 3
    $\begingroup$ 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. $\endgroup$
    – Pål GD
    Jun 18, 2020 at 14:04
  • $\begingroup$ +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.) $\endgroup$
    – chrylis -cautiouslyoptimistic-
    Jun 19, 2020 at 1:01
  • 1
    $\begingroup$ @BeanGuy Yes you are right, more or less. $\endgroup$
    – Caleb Stanford
    Jun 19, 2020 at 12:00
8
$\begingroup$

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.

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

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.

For completeness, I'll list a summary of the table of contents as well (see this Google books preview for the full table):

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
Sadil Vadhan, Probabilistic Proof Systems - Part I
Madhu Sudan, Probablistically Checkable Proofs
Improve this answer
$\endgroup$
4
  • $\begingroup$ That is not an introductory text, nor a comprehensive reference, but rather a collection of advanced topics. $\endgroup$
    – einpoklum
    Jun 19, 2020 at 14:47
  • $\begingroup$ @einpoklum I don't claim that this text is either, nor a replacement for them. It is suitable for self study for (somewhat advanced) mathematics students, which was what the question asked. $\endgroup$
    – Discrete lizard ♦
    Jun 19, 2020 at 15:27
  • $\begingroup$ The thing is, it is suitable, I belive, only for someone who already has a decent grasp of complexity theory. $\endgroup$
    – einpoklum
    Jun 19, 2020 at 15:37
  • $\begingroup$ @einpoklum Fair enough. I disagree, since I personally was able to read the book with barely any background in complexity theory, but this may be different for others. $\endgroup$
    – Discrete lizard ♦
    Jun 19, 2020 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.