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