An anonymous commenter on my last post asks:
isn’t the real problem with complexity theory that the resulting mathematics is usually superficial and shallow?
does this make it less fun to do complexity theory?
are complexity theorists ever saying something deep?
Later, the same commenter writes:
i’m just curious because I don’t really understand how I feel about the issue myself.
maybe we should start with something more basic. can we all agree that “logic” (i.e. foundations of math) is pretty boring and flavorless?
sure, we all got that little rush when we heard the story of the “fall of mathematics” in the early 20th century … and then maybe again with the axiom of choice, continuum hypothesis, independence, forcing, and various incompleteness theorems.
but is logic actually fun to do? on an emotional level, do you achieve understanding, intuition?
Alright, look, anonymous. You’ve nailed why I don’t work on logic myself — besides not understanding what the big, meaty open problems are. For me, frankly, reading about logic (or recursion theory, or programming language semantics, or distributed computing) has always felt like sipping broth. Sure, it might be delicious broth. In the case of (say) Gödel and Cohen’s independence results, it might even be the best broth I’ve ever tasted. But eventually I hanker for some noodles, some carrots, maybe some complex numbers or a Cauchy-Schwarz inequality. I mean, how long can a person go without bounding anything?
But you see, anonymous, that’s what I like about complexity. It packs the same theological punch as logic does, but it’s got math in it too. And I’m not just talking combinatorics and graph theory. Let me put it to you this way:
You like groups? We got groups.
You like vector spaces? We got them too.
But what about number theory? Finite fields? Fourier transforms? Continued fractions? “Shor.”
Eigenvalues? Chebyshev polynomials? Gaussians? Random walks? Lattices? Convex polytopes? Banach spaces? Metric embeddings? You better believe it.
Or how about this, anonymous: what’s your favorite constant? π? e? The golden mean? Maybe 0.288…=(1/2)(3/4)(7/8)(15/16)…? Becoming a complexity theorist doesn’t mean bidding any of them goodbye.
Look, we even got knots, braids, manifolds, unitary representations, varieties, cohomologies, plethysms — alright, maybe not so much of the last few. But if your favorite mathematical object isn’t in stock, bring it yourself! That’s the thing about complexity: anything is fair game if it yields a new upper or lower bound. The reason it’s so hard to prove P!=NP is precisely that a fast SAT algorithm could be hiding anywhere in the math library.
Now let me turn the tables, anonymous. Can you name a subfield of math that involves so many different kinds of math?