Review of « Complexity Theory’s 50-Year Journey to the Limits of Knowledge »

The article «  Complexity Theory’s 50-Year Journey to the Limits of Knowledge »  [1] provides a fascinating review of the study of the P versus NP problem, especially tracing it back to Hilbert’s Project, where the Entscheidungsproblem appeared, and relating the P versus NP problem to the work of Gödel, Turing, and others, which gives the article an openness that is hard to see in similar articles! 

The article is developed by the research career of Marco Carmosino, now a theoretical computer scientist at IBM: moving from an interest in Gödel's work to the study of the P versus NP problem. Faced with years of stagnation in the study of the P verses NP problem, Carmosino says, "It's one of the most obvious facts in theoretical computer science that when you come across a phenomenon that is so persistent, you need some explanation." In an effort to break out of the P verses NP problem dilemma, Carmosino and some scholars have turned to the "Minimum Circuit Size Problem" (MCSP), focusing their attention on the meta-complexity of the P verses NP problem and making some of the most recent advances.

The MCSP problem is intrinsically linked to the SAT problem, which has figured prominently in the study of verses NP problems:

1. SAT problem (boolean SATisfiability problem):

Given a Boolean formula F expressed as CNF, determine whether F is satisfiable, i.e., find the Boolean variable truth-value assignment that makes the formula F true.

Example 1

F= (p∧ q) ∨ (p ∧ r) ∨(q ∧ r)

F is satisfiable with four solutions:

p =0, q=1, r=1; 

p =1, q=0, r=1; 

p =1, q=1, r=0; 

p =1, q=1, r=1

The truth table for F is given below:

 

2. MCSP Problem (Minimum Circuit Size Problem):

Given a truth table of a Boolean formula A, find a formule with the minimum number of logical operators.

Example 2

Given a truth table: 

This truth table can be expressed as a formula with 15 logical operators:

(¬p ∧ q ∧ r) ∨ (p ∧ ¬q ∧ r) ∨(¬p ∧ ¬q ∧ r) ∨(p ∧ q ∧ r)

It can also be expressed as a formula with 5 logical operators:

(p∧ q) ∨ (p ∧ r) ∨(q ∧ r)

It can also be expressed as a formula with 4 logical operators:

(p∧ q) ∨(r ∧ (p ∨ q))

People encountered the so-called "natural proof barrier" on their way to solving the SAT problem, so they turned to the MCSP problem of circuit complexity. « My understanding is that people began working on circuit complexity because they decided that Turing machines were too complicated», says Ryan Williams, a complexity theorist at MIT.

Compared to the SAT problem, the MCSP problem focuses more on the detailed study of the problem structure, which may lead to a deeper understanding of the computational structure of the NP problem, and is undoubtedly a meaningful direction of research. However, it may be putting the cart before the horse to avoid Turing machines because of the study of the MCSP problem, since it is in Turing machines that the NP problem has its origins (see the figure above)!

On the other hand, there should be some reasons why people try to avoid Turing machines and Turing's work around them (1936 paper). I think that one of the major reasons for this is that Gödel's work prevents one from recognizing the true "undecidable propositions" in formal systems, since Gödel claimed that paradoxical propositions such as « this proposition is unprovable" are the normal "undecidable propositions" in formal systems, and this prevented one from delving deeper into Turing's machine and Turing's illuminating work on the essence of undecidable propositions (1936). Typical of this is the reduction of Turing's work to a cartoon version of the "halting problem", the proof of which is a replica of Gödel's proof but not Turing's work!

Fifty years later, the question (the P verses NP problem) remains unanswered. Kabanets likened reasoning about the limits of computation to surveying a vast territory without any sense of the big picture. A being of unlimited computational power could peer down from a mountaintop and take in the whole landscape at once, but mere mortals can’t count on that kind of advantage. “Those of us at the bottom of the mountain can try to maybe jump up and down for a better view,” he said.

I think that it is not a « superman »  with unlimited computational power who can see the whole landscape from a mountaintop, but rather a « mortal »  with «  systems thinking »  who can get a large vision, and the fact that people are now realizing the meta-complexity of the verses NP problem shows that there is a move towards a broader view of systems thinking, which is what we are hoping for when we initiate the revisiting of Gödel’s incompleteness theorem at the World Congress of Philosophy in Rome in 2024:

• To promote academic and public reflection on Gödel's Incompleteness Theorems, we propose to revisit these theorems from different perspectives such as philosophy, epistemology, psychology, logic, mathematics, algorithmic theory and artificial intelligence, to penetrate into the original proof of the theorems in Gödel's 1931 paper, to go beyond the limits of our thinking, and to confront the malaise involved in Gödel's proof together. 
• We believe that the aspiration for truth and the seeking of truth is the most fundamental way to dissolve malaise, a quality indispensable when caring for the future of our world, …

The New Year is an opportunity and possibility to bring a new vision to life, and lucky are those who have a clear vision. May we go into 2024 with such a clear vision!

Reference :

[1] Complexity Theory’s 50-Year Journey to the Limits of Knowledge

By BEN BRUBAKER，August 17, 2023

https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/