# How does one "understand" complexity theory?

There's a famous quote by Bob Thomason about Grothendieck that he tried to understand algebraic geometry whilst everyone else was super-fixated on trying to prove theorems. Complexity theory, as one learns it at a graduate level (or maybe as far as human knowledge of it goes), seems to be more so a collection of isolated results. There is some amount of "coherence" and a web of connections, but it is not as "coherent" as fields like group theory or the theory of finite fields. How does one go about building a strong understanding of complexity theory as a "whole" rather than as a collection of results?

• Wait an additional century or two. Jan 27 at 16:16
• You can approach the study of complexity (including computability) as the study of complexity classes, which are, in a sense, natural phenomena, to be studied much as biologists study taxonomies of animal species. From this perspective the field seems to me to be bring relative coherence to a wide variety of computational problems. E.g. consider P vs NP, or decidable questions vs undecidable ones. Another perspective is that complexity theory is about the relationships between problems, as opposed to about particular problems. Jan 27 at 17:16
• I disagree with the downvotes to close. (Sure, it's a soft question, and marked as such, but it is one that any grad student researching TCS could easily have, so I think it belongs on this site. And while it may lead to somewhat opinionated answers, it is at heart a question about what & how to learn more, and how to think about these things in a more advanced way, that could benefit from answers from experts, even if they are somewhat opinionated. This site has many such Qs on it and they are often very valuable!) Feb 2 at 16:28

Finite fields are a very rare exception. Very few theories in mathematics are as complete as the theory of finite fields. ("Complete" in some informal sense, not in the sense of "logical completeness".) We know exactly what they are: a finite field exists iff its order is a prime power, and all finite fields of the same order are unique up to isomorphism, all finite degree extensions are Galois, the absolute Galois group is always generated by the Frobenius. $$GF(p^a)$$ embeds into $$GF(p^b)$$ iff $$a | b$$. etc. etc. (However, even here, basic open questions remain. Like: given $$p$$, how hard is it to construct irreducible polynomials of all degrees such that the aforementioned embeddings are "obvious" given the polynomials you chose.)
I think in any of these fields, as with complexity, one way you get to start understanding them as "whole" is by seeing as many connections as you can between seemingly-isolated results. Reductions in computational complexity give us a particularly nice way of seeing such relations (the reduction from SETH to Longest Common Subsequence comes to mind - you'd think that algorithms for SAT and the DP algorithm for LCS have nothing to do with one another, but surprise!). Or the way William's NEXP not in ACC$$^0$$ result ties together so many seeming-unrelated algorithmic techniques (diagonalization, rectangular matrix multiplication, Beigel-Tarui-Yau, short witnesses, ...). There are, by now, lots of connections between various sub-branches of complexity, such as connections between communication complexity, query complexity, proof complexity, algebraic complexity vs Boolean complexity, hardness vs randomness, matrix rigidity, extension complexity of polytopes, etc.