Reverse math shows why hard problems are hard(quantamagazine.org)
quantamagazine.org
Reverse math shows why hard problems are hard
https://www.quantamagazine.org/reverse-mathematics-illuminates-why-hard-problems-are-hard-20251201/
57 comments
The first time I saw the Pigeonhole Principle was in the following:
Problem: A plane has every point colored red, blue, or yellow. Prove that there exists a rectangle whose vertices are the same color.
Solution: Consider a grid of points, 4 rows by 82 columns. There are 3^4=81 possible color patterns of columns, so by the Pigeonhole Principle, at least two columns have the same color pattern. Also by the Pigeonhole Principle, each column of 4 points must have at least two points of the same color. The two repeated points in the two repeated columns form a rectangle of the same color. QED.
The Pigeonhole Principle is very neat. It would be hard not to use it for the proof.
Partly that article argues against proof by contradiction which does seem to be overused.
Problem: A plane has every point colored red, blue, or yellow. Prove that there exists a rectangle whose vertices are the same color.
Solution: Consider a grid of points, 4 rows by 82 columns. There are 3^4=81 possible color patterns of columns, so by the Pigeonhole Principle, at least two columns have the same color pattern. Also by the Pigeonhole Principle, each column of 4 points must have at least two points of the same color. The two repeated points in the two repeated columns form a rectangle of the same color. QED.
The Pigeonhole Principle is very neat. It would be hard not to use it for the proof.
Partly that article argues against proof by contradiction which does seem to be overused.
A grid with 19 columns is enough. Every column at worst has all 3 colors, one of them used twice. Once we fix that one color, there are C(4,2)=6 ways of filling out the rest of the entries. Since there are 3 colors, there are exactly 6*3=18 worst possible columns. With 19 columns a repetition is guaranteed, yielding the desired rectangle.
For fun, try strengthening the result to a square.
For fun, try strengthening the result to a square.
[deleted]
Wow, this works for any number of colors.
Yes it does :)
What a fun little result.
What a fun little result.
Unless by plane they mean airplane, since in curved 3d surface this is not automatically given to be true.
Even if it was talking about airplanes, it doesn’t mention “surface”. So it would still hold, given that airplane parts aren’t infinitely thin.
Topologically, an airplane is identical to a universe of curvature=+1. Since the size of the grid versus the airplane/universe is not given, I will assume there are infinitely many grid points.
sudoku is just pigeonholing then
I love Dijkstra's writing, but I don't think this is his strongest piece. In general parlance, when we say "by piegonhole" we mean "any variant of it". I'd still call what he's doing "piegonhole" lol. You can even further generalize it, e.g. by making expected value arguments.
This is not uncommon: we can say that "by the fundamental theorem of algebra" two polynomials of degree N that agree on N+1 points are identically equal. "By induction" includes Cauchy induction, sometimes with "this and that are the same" we mean "up to isomorphism" and so on.
The advice he ends on is extremely solid, though:
This is not uncommon: we can say that "by the fundamental theorem of algebra" two polynomials of degree N that agree on N+1 points are identically equal. "By induction" includes Cauchy induction, sometimes with "this and that are the same" we mean "up to isomorphism" and so on.
The advice he ends on is extremely solid, though:
The moral of the story is that we are much better off with the neutral, general standard procedure: name the unknown(s) so that you can formalize all conditions given or to be established and simplify by formula manipulation.
Combining that with OP article, the obstruction to showing hardness is therefore not technical but foundational- ie. the required axiom lies outside the standard minimal toolkit
Wow. I thought the metaphor was stupid when I was taught this in college, and only now, decades later, I find out Dijkstra agreed.
Interesting! Were there other examples from your course that had similar delays in insight? What changed your perspective?
Also makes an appearance in the recent thread about how "every mathematician only has a few tricks": https://mathoverflow.net/questions/363119/every-mathematicia...
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.
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.
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.
That's par for a field whose name seems to have been inspired by "reverse-engineering", which by construction doesn't try to understand products that have not yet reached the market :)
Well, but you can also reverse engineer nature (or the output of gradient descent) or the products of an adversary.
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 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've grown to see math as far more pattern matching than I remember it as a kid. I think that explains why "rote memorization" works more than folks want to admit for it.
This doesn't end at kid level maths either, I have seen people get bachelors and masters in maths without understanding much of it intuitively or being able to apply it.
Mostly because they have rote memorised it (and partly because much of the education system is a game to be played e.g. speaking with professors during office hours can give very strong hints to exams).
Mostly because they have rote memorised it (and partly because much of the education system is a game to be played e.g. speaking with professors during office hours can give very strong hints to exams).
My professor said this was an inevitability that holds people back who don't understand it is. After a certain point, you can't understand it all, because actually understanding it requires understanding the 1000 page proof. After a certain point, in maths, you must rote memorize the tools, add them to your belt, and trust the centuries of work before you, so you can apply them to your problems. It serves no purpose to "understand" them, many cannot be put into an intuitive framework, and attempting to make "understanding" a prerequisite to your progress will mean you will eventually fail out of the program.
"Young man, in mathematics you don't understand things. You just get used to them."
John von Neumann
John von Neumann
Right, I've also seen people that couldn't get some higher math items because they haven't learned to recognize some things on sight. Curves are a good example. You should be able to roughly sight identify basic curves. Or distributions based on their shape. With obvious caveats.
I suspect this is a lot like being able to recognize a piece of art to the artist by sight. Strictly, not required. But a lot of great artists can do it.
For real fun, I saw an interview with Magnus Carlsen where someone was quizzing him on famous games. He was able to say the match on the first 2-3 moves a remarkable number of times.
I suspect this is a lot like being able to recognize a piece of art to the artist by sight. Strictly, not required. But a lot of great artists can do it.
For real fun, I saw an interview with Magnus Carlsen where someone was quizzing him on famous games. He was able to say the match on the first 2-3 moves a remarkable number of times.
I wish this interesting story was related to the article.
If I may share, the stuff occurring in a computer would not be qualified as math … math is more about intuition and the sense of describing things in quantitative languages …
Neuroscience suggests global connectivity changes after 40 instead of specialized areas. Overall declines do not start until late 40s though.
I started going down that road decades ago myself. I had a degree in computer science already, but I'd only learned just enough math to graduate and then forgotten everything, deliberately.
Years after I graduated, I was browsing comp.lang.java (I think it was) and somebody asked for help developing an applet that could draw a 3-D arrow that could orient itself in any direction. For some reason, that sounded interesting to me, so I started trying to work on it and I realized I needed to go back and re-learn all of that "point-slope" stuff that I'd made a point of learning just enough of to squeak through college.
That sent me down the path of re-learning all the things I now wish I'd put more effort into learning when I was a teenager. I ended up working through my old undergraduate calculus textbook a few times and I understand undergraduate calculus _really_ well now. I was able to coach both of my kids through high school calculus and they both remarked that none of their friends parents were able to help them beyond algebra.
It makes me wonder how many people are great (or even adequate) at math and how many are just faking it - as interesting as I now find it, math skills aren't actually very practically useful.
Years after I graduated, I was browsing comp.lang.java (I think it was) and somebody asked for help developing an applet that could draw a 3-D arrow that could orient itself in any direction. For some reason, that sounded interesting to me, so I started trying to work on it and I realized I needed to go back and re-learn all of that "point-slope" stuff that I'd made a point of learning just enough of to squeak through college.
That sent me down the path of re-learning all the things I now wish I'd put more effort into learning when I was a teenager. I ended up working through my old undergraduate calculus textbook a few times and I understand undergraduate calculus _really_ well now. I was able to coach both of my kids through high school calculus and they both remarked that none of their friends parents were able to help them beyond algebra.
It makes me wonder how many people are great (or even adequate) at math and how many are just faking it - as interesting as I now find it, math skills aren't actually very practically useful.
Backwards game of life: https://m.youtube.com/watch?v=g8pjrVbdafY
I couldn't see any citations or references in that video or its description. It presents it as him solving the problem himself, but I'm sure other people have written about solving the Game of Life in reverse with SAT solvers prior to this...
Edit: here's a paper on it from 2006, https://link.springer.com/chapter/10.1007/978-3-540-76928-6_...
Edit: here's a paper on it from 2006, https://link.springer.com/chapter/10.1007/978-3-540-76928-6_...
Garden of Eden[0] is a related concept where time-reversal comes up. Mentions NFAs, DFAs, backtracking and brute-force analysis. I see no mention of it but the latter was probably doing custom SAT implicitly, even if there was no access to our nice fast modern solvers.
[0]: https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_autom...
[0]: https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_autom...
The approach reminds me of NP-Completeness (Computational harness vs mathematical-proving hardness). Am I over-simplifying?
You’re right on the money. It’s intimately tied to computability theory, complexity theory’s more abstract sibling (I.e. the Halting problem and further Turing degrees). Both rely on the core techniques of diagonalization and reductions. The meat of it can differ a lot because estimating time bounds and determining logical equivalence rapidly become different problem spaces, so it’s not like results in one are really applicable to the other. But a researcher in one will usually be well versed in the other.
I would say that's on the wrong track and that "hard" is the wrong term for what reverse math (RM) tells you about problems. RM studies what axioms you need to prove a given theorem, but it's more like showing that "to pound in a nail of size X you need a hammer of size Y and a smaller hammer just can't do it", than saying pounding in the nail is difficult or complicated. Once you have the big enough hammer, pounding the nail can be very simple.
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
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'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.
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'm not sure if you're just choosing intentionally obtuse verbiage or if you're actually saying something completely incoherent.
"Overall Complexity" is a meaningless term without you defining it. I suppose you mean that there is some lower bound limit to the amount of work relative to a model of computation, but this is a trivial statement, because the limit is always at least no work.
We have many problems where we don't know the least upper bound, so even an interesting formulation of your idea is not necessarily true: work need not be conserved at the least upper bound, because reaching the bound may not be possible and epsilon improvement might always be possible.
Finally, algorithmic complexity is the wrong analogy for reverse mathematics anyway.
"Overall Complexity" is a meaningless term without you defining it. I suppose you mean that there is some lower bound limit to the amount of work relative to a model of computation, but this is a trivial statement, because the limit is always at least no work.
We have many problems where we don't know the least upper bound, so even an interesting formulation of your idea is not necessarily true: work need not be conserved at the least upper bound, because reaching the bound may not be possible and epsilon improvement might always be possible.
Finally, algorithmic complexity is the wrong analogy for reverse mathematics anyway.
To give an example, we consider that binary search requires less work than a linear search. But there are costs and usecase considerations involved. Insertion of new recod need to use binary search to keep the data sorted. Also if the number of lookups is far less than number of records, the overall cost is more than appending and linear search. That's what I mean by by moving the complexity around.
A problem scenario doesn't have absolute characteristics. It's relative to your way of looking at it, and your definition of a problem.
A problem scenario doesn't have absolute characteristics. It's relative to your way of looking at it, and your definition of a problem.
You are right, but this doesn't mean that the amount of work is conserved as your original message implies. The correct statement would be that "algorithmic complexity is just one aspect of actual practical complexity and an algorithm with better algorithmic complexity can end up performing worse in reality due to practical considerations of the data and the processor doing the computations".
> Complexity of traveling salesman problem depends on what you consider as the problem space - number of cities or number of connections between cities.
lmao what?
lmao what?
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
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
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.
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.
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.
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.
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.
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.
[deleted]
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.
https://www.cs.utexas.edu/~EWD/transcriptions/EWD10xx/EWD109...