Chen Lijie, a genius from Tsinghua University's Yao Class, joins hands with post - 2000s talents to break the situation through reverse thinking and overturn a 50 - year - old computer problem.
A genius from Tsinghua University's Yao Class has once again set off a storm in the field of theoretical computer science!
For the past 50 years, top scientists have been struggling with computer complexity problems such as the "Traveling Salesman Problem" without making much progress.
Why can't these problems be proven?
Actually, the answer lies in the field of "metamathematics".
Just last year, a paper titled "Reverse Mathematics Below the Turing Jump" was quietly published online.
The paper has only three authors: Lijie Chen from Tsinghua University's Yao Class, undergraduate student Jiatu Li, and well - known computer scientist Igor Carboni Oliveira.
Paper link: https://eccc.weizmann.ac.il/report/2024/060/
Instead of sticking to the traditional approach of deriving theorems from axioms, they took a different path and adopted the method of "reverse mathematics" in "metamathematics".
Surprisingly, they found that many seemingly unrelated theories are actually completely equivalent in terms of underlying logic.
For example, the "Pigeonhole Principle" is equivalent to the "palindrome lower bound" of Turing machines.
This paper has completely overturned people's "worldview".
In the past half - century, the idea of computer scientists to "use stronger axioms to prove more difficult theorems" was actually off - track from the start.
Turn mathematics "upside down"
Overturn the millennium - old thinking paradigm
When it comes to those "tough nut" problems, computer scientists seem to hit a wall.
Take the famous "Traveling Salesman Problem" as an example. On the surface, it is just a combinatorial optimization problem:
Find the shortest route on a map that passes through each city exactly once and returns to the starting point.
However, once the number of cities increases slightly, scientists begin to doubt that there is no good solution. The problem is, no one knows how to prove this.
In the past 50 years, the top figures in the field of computational complexity theory have tried to turn this "intuition" into solid mathematical theorems.
In fact, they have failed again and again, unable to find any breakthrough.
This has also made them increasingly ponder a related but more confusing question: why do the proofs always fail?
"Metamathematics" takes the proof itself as the object of study.
When researchers use "metamathematics" to study complexity theory, they try to figure out -
What conclusions about computational difficulty can or cannot be proven using different sets of axioms.
Why they always fall short in proving that "a problem is difficult".
In April 2024, this paper did something that no one had ever dared to think of: the three - person team completely reversed the millennium - old thinking paradigm of mathematics.
The traditional approach is to start with a set of axioms and derive a series of theorems.
Now, they did the opposite - they replaced one of the axioms with a theorem and then tried to prove the replaced axiom.
As the title of the paper suggests, this process is called "Reverse Mathematics".
It proves that a large number of seemingly unrelated "complexity theorems" are actually logically equivalent.
Marco Carmosino, a complexity theorist at IBM, was shocked when he first saw the paper. "I was amazed that they could achieve so much," he said.
Anyone who reads it will surely say, "It was this paper that dragged me into the pit of'metamathematics'!"
Pigeonproof, heretical
The story begins in the summer of 2022.
At that time, Lijie Chen was about to graduate with a PhD from MIT. Finding himself with a lot of free time, he decided to spend a few months delving into metamathematics.
He said, "Since I was graduating and had fewer research tasks, I thought I should learn something new."
As he read, Lijie Chen began to think about a branch of complexity theory - communication complexity.
It mainly studies how much information two or more people must exchange to complete a certain task.
In communication complexity, the simplest problem is the "equality problem", which is like a cooperative game:
Two players each hold a string of 0s and 1s. The goal is to figure out whether the other person's string is exactly the same with the least amount of communication.
The most stupid way is for one player to send the entire string to the other for checking.
Complexity theorists proved decades ago that there is no better way.
To solve the "equality problem", one has to send at least as many bits as the length of the string. Theorists call this the "lower bound" of the required communication volume.
Lijie Chen was not interested in the "lower bound" itself, but in how researchers proved it.
All known proofs rely on a simple theorem - the "Pigeonhole Principle".
The principle states that if you put a bunch of pigeons into fewer holes than the number of pigeons, at least one hole will have more than one pigeon.
This may sound like nonsense, but it is a very powerful tool in complexity theory and many other fields.
So, Lijie Chen acutely captured an important clue -
The connection between the "equality problem" and the "Pigeonhole Principle" might be two - way.
It is easy to prove the lower bound of the equality problem using the Pigeonhole Principle. But can we do the opposite, use the lower bound to prove the Pigeonhole Principle?
Strange equality
So, Lijie Chen invited Jiatu Li, an undergraduate student from Tsinghua University who had just collaborated with him on a paper, and they started a new exploration.
To make this connection mathematically sound, they had to choose a set of axioms as the "foundation".
They chose a popular set of axioms called PV₁ and started the "reverse" process.
Since PV₁ is strong enough to independently prove some important theorems in computational complexity, if an additional axiom in the form of a specific version of the "Pigeonhole Principle" is added to PV₁, the lower bound of the "equality problem" can be proven.
In December 2022, they succeeded!
The result verified Lijie Chen's initial conjecture: swapping the positions of the theorems still makes the proof valid.
In the PV₁ logical framework, the two theorems are completely equivalent.
When they talked to Igor Oliveira, a complexity theorist at the University of Warwick, they suddenly realized -
The method of "reverse mathematics" may also be applicable to other seemingly unrelated areas in complexity theory.
In the following months, they systematically proved that many other theorems are also equivalent.
Lijie Chen said, "At the beginning, there were only two equivalent things we wanted to prove, but now we have woven a large net."
The most amazing connection discovered by this team is between the same version of the "Pigeonhole Principle" and one of the earliest theorems that students learn in an introductory course on complexity theory.
This classic theorem sets a lower bound on the time required for a single - tape Turing machine, a theoretical computer, to determine whether a string of 0s and 1s is a palindrome (reads the same forwards and backwards).
"Reverse Mathematics" proves that within the PV₁ framework, this "palindrome lower bound" theorem is equivalent to the Pigeonhole Principle.
Lijie Chen said in disbelief, "If you told me this result directly, I wouldn't believe it. It sounds too absurd."
This conclusion is so surprising because the two theorems seem so different on the surface.
The "Pigeonhole Principle" has nothing to do with computation in essence; it is a simple principle about counting.
The palindrome lower bound is a statement about a specific computational model.
This new result means that these seemingly narrow - scope theorems are actually much more general and fundamental than they appear.
Oliveira said, "This shows that the complexity lower bounds we want to understand are actually more fundamental."
Unknown territory, still need to lay a solid foundation
Fortunately, this new "equivalence network" has also helped scientists see the limitations of PV₁.
People have long believed that the "Pigeonhole Principle" cannot be proven using only the axioms of PV₁.
So, the results of the paper mean that most of the other equivalent theorems in the network are also likely to be unprovable in PV₁.
Ján Pich, a complexity theorist at the University of Oxford, sighed, "I think it's beautiful."
But he also reminded that the method of "reverse mathematics" may be most suitable for revealing new connections between already - proven theorems.
"For statements that we don't know how to prove yet, at present, it doesn't tell us much about their complexity."
Understanding this unknown territory is still a distant goal for "metamathematics" researchers.
However, this has not dampened Jiatu Li's enthusiasm for this subject.
After entering MIT for postgraduate studies in 2023, he recently wrote a 140 - page metamathematics guide for complexity theorists.
Paper link: https://eccc.weizmann.ac.il/report/2025/086/
This is also a microcosm of a major trend: even after decades of being in the shadows, "metamathematics" is increasingly attracting the attention of a wider group of researchers, who are bringing new perspectives to this field.
Carmosino said, "People are tired of being stuck. It's time to take a step back and clarify the foundation."
Author introduction
Lijie Chen
Lijie Chen is an assistant professor in the Department of Electrical Engineering and Computer Science (EECS) at the University of California, Berkeley, and is also a member of the Berkeley Theory Group.
As early as in high school, Lijie Chen became a legend in the informatics competition circle, showing programming talent and mathematical insight beyond his peers.
In the 2012 NOI competition, Lijie Chen stood out with a gold medal and secured a spot at Tsinghua University through the recommendation system in advance.
Then, at the 25th IOI, he won the global first place with an amazing score of 569 out of 600.
He has long dominated international programming platforms