Reverse math shows why hard problems are hard

I recently had, for various reasons, improve my math skills.

I was surprised at how difficult I found math. Now, I was never really great at math; logic and calculation in the head I could do fairly well (above average), but just foundational knowledge was hard and mathematical theory even harder. But now I even had trouble with integration and differentiation and even with understanding a problem to put it down into a formula. I am far from being the youngest anymore, but I was surprised at how shockingly bad I have become in the last some +25 years. So I decided to change this in the coming months. I think in a way computers actually made our brains worse; many problems can be auto-solved (python numpy, sympy etc...) and the computers work better than hand-held calculators, but math is actually surprisingly difficult without a computer. (Here I also include algorithms by the way, or rather, the theory behind algorithms. And of course I also forgot a lot of the mathematical notation - somehow programming is a lot easier than higher math.)

Whenever the pigeon-hole principle is name dropped, we should also drop Dijkstra's commentary The undeserved status of the pigeon-hole principle.

https://www.cs.utexas.edu/~EWD/transcriptions/EWD10xx/EWD109...

Specifically, reverse math (a subset of metamathematics which looks at swapping axioms and theorems) allows us to show that some hard problems are equivalent to each other.

EDIT: I think this line is the most telling:

> But he cautioned that the reverse mathematics approach may be most useful for revealing new connections between theorems that researchers have already proved. "It doesn’t tell us much, as far as we can say, about the complexity of statements which we do not know how to prove."

So, at this point, it helps us understand more about problems we already understand a little about, but nothing yet about new problems.

Backwards game of life: https://m.youtube.com/watch?v=g8pjrVbdafY

The approach reminds me of NP-Completeness (Computational harness vs mathematical-proving hardness). Am I over-simplifying?

I'm pretty far away from learning about these things in school, but this made me wonder on the connection between the mentioned communication complexity lower bound and special relativity limits on how fast information can travel.

Overall complexity (work required) is a conserved quantity. You can move it around and claim that a new algorithm has reduced the complexity, but in essence it has shifted the complexity elsewhere.

Also, whether some problem has polynomial complexity or exponential complexity depends on what you consider as the problem space. Complexity of b^c is polynomial if b is the problem space and exponential if c is the problem space.

Complexity of traveling salesman problem depends on what you consider as the problem space - number of cities or number of connections between cities.

The Travelling Salesman Problem in 1 dimension, on a line, is trivial, I wonder what the connection is between the dimensions and the hardness of problems like this.

[dead]