5
$\begingroup$

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?

$\endgroup$
3
  • 4
    $\begingroup$ Wait an additional century or two. $\endgroup$
    – Tassle
    Jan 27 at 16:16
  • 5
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Jan 27 at 17:16
  • 5
    $\begingroup$ 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!) $\endgroup$ Feb 2 at 16:28

1 Answer 1

5
$\begingroup$

It's a nice question, but before partially answering it I want to question part of the premise.

My main thesis here is that all mathematical fields are actually just loosely coherent collections of "isolated" results, once you get deep enough into them. The more background a field requires, the deeper you have to go before you see that. As combinatorics and computational complexity require very few definitions and background, you start to see these loosely coherent collections of isolated results sooner. In contrast, in a field like group theory, there is first a lot of structure to be presented (normal subgroups, quotients, direct products, semidirect products, group extensions, group actions, etc.). But once you get past that structure, you end up with a bunch of results that again feel like loosely coherent collections of isolated results. Same with algebraic geometry (there are so many results in algebraic geometry about specific varieties in low dimensions or low codimensions).

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.)

The theory of regular languages and automata is another fairly complete field, though again, there also some basic questions remain.

I think part of the reason most fields seem like such loosely coherent collections of isolated results is that they objects they study are in fact quite complicated, so getting such a "complete" theory may be literally impossible. In the case of complexity theory, the objects under study are really algorithms, and algorithms are definitely complicated beasts!

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.

$\endgroup$

Your Answer

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

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