论文标题
50年的计算复杂性：Hao Wang和计算理论
50 Years of Computational Complexity: Hao Wang and the Theory of Computation
论文作者
论文摘要
如果图灵（Turing）在1936年的开创性论文奠定了计算理论（TOC）的基础，那么说库克（Cook）在1971年的论文“定理的复杂性证明程序”并没有夸张，[4]率先研究了计算复杂性的研究。因此，作为一个独立研究领域的计算复杂性现在已经有50年的历史了（2021年），如果我们从库克的文章中约会。今年恰逢库克的导师Hao Wang诞辰100周年，这是最重要的逻辑学家之一。本文追溯了计算复杂性的起源，同时，试图弄清王在此过程中扮演的工具作用。
If Turing's groundbreaking paper in 1936 laid the foundation of the theory of computation (ToC), it is no exaggeration to say that Cook's paper in 1971, "The complexity of theorem proving procedures", [4] has pioneered the study of computational complexity. So computational complexity, as an independent research field, is 50 years old now (2021) if we date from Cook's article. This year coincides with the 100th birthday of Cook's mentor Hao Wang, one of the most important logicians. This paper traces the origin of computational complexity, and meanwhile, tries to sort out the instrumental role that Wang played in the process.
