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.
> So, at this point, it helps us understand more about problems we already understand a little about, but nothing yet about new problems.
I don't think this caution makes any sense!
The more we learn about theorem/axiom equivalences (or more generally, the lattice of such connections) between existing proofs, the more insights we will gain into how unproved conjectures may relate to existing proofs or each other.
Only in the strictest possible sense does saying showing X tells us nothing about showing Y. Meaning a proof or identification of X is not a proof or identification of related thing Y. But that is an obviously pedantic statement.
Not to critique the person being quoted. I feel like an offhand remark may have got unduly elevated by being quoted in a "two-sides of a story" writer's dramatization reflex.
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.
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.
In the Game of Life community, people use "c" to refer to the speed at which a GoL figure can travel, which is at most 1 in the vertical direction, and 1 in the horizontal direction.
Thanks for pulling that thread with me. It would be interesting to see if the lower bound on information needed is ever swappable with the upper bound on the speed of information transfer.
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.
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.)
I usually don't say this about Quantamagazine, but thank you for covering and informing me about this. The perspective is insightful and after comprehending the concepts a little more, they are not a hyperbole. I'm currently reading through the mentioned paper, "An Introduction to Feasible Mathematics and Bounded Arithmetic for Computer Scientists" by Jiatu Li and I believe that it's greatly elucidating.
If you're reading the paper, I recommend Section 1.3 where it goes over the examples of Binary Search and Dijkstra. The idea that "natural numbers are encoded by binary strings just as other data structures" in the preface is prevalent in their constructions of their proofs. As a computer scientist, this is great because I intuitively recognize that both algorithms and memory consist of only 1's and 0's underneath all the abstractions and code.
This work ties together practical applications and complexity theory to create a new bridge in mathematics that I'm excited about exploring. I'm especially interested in reverse mathematics applied to space complexity.
Here's some additional resources I found on this,
Talk by Jiatu Li, joint work with Lijie Chen, Igor Carboni Oliveira
Title: Reverse Mathematics of Complexity Lower Bounds
https://www.youtube.com/watch?v=g5EqAgDxxE0
I think the reason this is interesting to mathematicians is that he was working with an axiomatic system that is fairly new, and _in particular_ is thought not to be strong enough to be able to prove the pigeon hole principle. Since he proved that all these other theorems are equivalent to the pigeonhole principle, all of those other theorems are probably also not able to be proven with PV1.
The pigeonhole principle informs us that if we have more pigeons than holes, some holes have two or more pigeons. But also that if we have fewer pigeons than holes, some holes will necessarily be empty.
Given two bit strings of length n, if we compare fewer than n pairs, we cannot tell whether they are equal. The strings being equal is the proposition a_0 = b_0 ^ a_1 = b_1 ^ ... ^ a_n-1 = b_n-1. You cannot simplify this formula such that any a_i or b_i primary is taken away.
And there's no clever trick you can do using eg hash functions or compression to shortcut the process? Of course the proofs that hash functions have collisions and there is no universal compression algorithm use the pigeonhole principle..
The shortcuts all revolve around the cases when the strings are different.
If we just do a zipper compare and the first pair of bits happens to differ, we are done, having looked at only two bits.
Similarly, we compute hash functions that sample only a small number of bits out of each string, and the hash codes don't match, we are done.
The worst case occurs when the strings turn out to be identical. We cannot make the correct verdict that the strings are identical without examining every bit; any bit we don't look at could be the same or different, and so we cannot announce a decision.
I wrote as my comment kind of as a rhetorical question, but perhaps in retrospect the connection between the string comparison problem the pigeonhole principle is not so surprising in the end.
Intellectually curious podcast did a piece on reverse math recently, only 5m but more detailed in places than quanta.
In a lot of ways this feels related to the development of noneuclidean geometry so it's kind of surprising it wasn't a hot topic sooner. Maybe it was waiting for a critical mass of computer scientists to come along, or maybe we just needed to run out of other low-hanging fruit so that foundational topics in complexity became more interesting
I didn't know and not mentioned in the article is that there are two different programs in reverse mathematics, one relating to classical mathematics, the other relating to complexity questions. Claude says this: not sure about accuracy
Let me clarify the relationship between PV₁ and reverse mathematics systems, as there are actually two different research programs here:
Two Different Programs
1. Classical Reverse Mathematics (over RCA₀)
The standard reverse mathematics program, pioneered by Harvey Friedman and Stephen Simpson, works over second-order arithmetic and studies which set existence axioms are needed to prove theorems of ordinary mathematics. The main systems form the "Big Five":
RCA₀ (Recursive Comprehension Axiom)
WKL₀ (Weak König's Lemma)
ACA₀ (Arithmetic Comprehension Axiom)
ATR₀ (Arithmetic Transfinite Recursion)
Π¹₁-CA₀ (Π¹₁ Comprehension Axiom)
2. Bounded Reverse Mathematics (over PV₁ or similar)
This is a separate program studying computational complexity rather than computability. It analyzes which theorems require which computational resources.
23 comments
[ 2.6 ms ] story [ 53.7 ms ] threadEDIT: 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.
I don't think this caution makes any sense!
The more we learn about theorem/axiom equivalences (or more generally, the lattice of such connections) between existing proofs, the more insights we will gain into how unproved conjectures may relate to existing proofs or each other.
Only in the strictest possible sense does saying showing X tells us nothing about showing Y. Meaning a proof or identification of X is not a proof or identification of related thing Y. But that is an obviously pedantic statement.
Not to critique the person being quoted. I feel like an offhand remark may have got unduly elevated by being quoted in a "two-sides of a story" writer's dramatization reflex.
https://www.cs.utexas.edu/~EWD/transcriptions/EWD10xx/EWD109...
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.
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.)
If you're reading the paper, I recommend Section 1.3 where it goes over the examples of Binary Search and Dijkstra. The idea that "natural numbers are encoded by binary strings just as other data structures" in the preface is prevalent in their constructions of their proofs. As a computer scientist, this is great because I intuitively recognize that both algorithms and memory consist of only 1's and 0's underneath all the abstractions and code.
This work ties together practical applications and complexity theory to create a new bridge in mathematics that I'm excited about exploring. I'm especially interested in reverse mathematics applied to space complexity.
Here's some additional resources I found on this, Talk by Jiatu Li, joint work with Lijie Chen, Igor Carboni Oliveira Title: Reverse Mathematics of Complexity Lower Bounds https://www.youtube.com/watch?v=g5EqAgDxxE0
Given two bit strings of length n, if we compare fewer than n pairs, we cannot tell whether they are equal. The strings being equal is the proposition a_0 = b_0 ^ a_1 = b_1 ^ ... ^ a_n-1 = b_n-1. You cannot simplify this formula such that any a_i or b_i primary is taken away.
If we just do a zipper compare and the first pair of bits happens to differ, we are done, having looked at only two bits.
Similarly, we compute hash functions that sample only a small number of bits out of each string, and the hash codes don't match, we are done.
The worst case occurs when the strings turn out to be identical. We cannot make the correct verdict that the strings are identical without examining every bit; any bit we don't look at could be the same or different, and so we cannot announce a decision.
In a lot of ways this feels related to the development of noneuclidean geometry so it's kind of surprising it wasn't a hot topic sooner. Maybe it was waiting for a critical mass of computer scientists to come along, or maybe we just needed to run out of other low-hanging fruit so that foundational topics in complexity became more interesting
Let me clarify the relationship between PV₁ and reverse mathematics systems, as there are actually two different research programs here: Two Different Programs 1. Classical Reverse Mathematics (over RCA₀) The standard reverse mathematics program, pioneered by Harvey Friedman and Stephen Simpson, works over second-order arithmetic and studies which set existence axioms are needed to prove theorems of ordinary mathematics. The main systems form the "Big Five": RCA₀ (Recursive Comprehension Axiom) WKL₀ (Weak König's Lemma) ACA₀ (Arithmetic Comprehension Axiom) ATR₀ (Arithmetic Transfinite Recursion) Π¹₁-CA₀ (Π¹₁ Comprehension Axiom) 2. Bounded Reverse Mathematics (over PV₁ or similar) This is a separate program studying computational complexity rather than computability. It analyzes which theorems require which computational resources.