在计算机领域中，最重要的是什么？对科学家来说，是计算理论。这跟大众关系很远，但是对计算机又至关重要。到目前为止，ACM已经发了12次图灵奖给计算理论，其重要性不言而喻。
最近江苏一个中专女生数学竞赛考了第12名，可以说是火遍全网了。但是，谁又懂她做的那些题呢？
恰好，本期的主人公，第17届图灵奖得主，也是数学家，搞计算复杂性理论的。这其实是一个数学分支，与普通人有一定的距离，具体来说，他是搞NP定理的。
对普通人来说，无关紧要。对科学家来说，至关重要。
计算复杂性理论可以确定一个问题能否被计算机以“合理的资源”求解。这跟可计算性理论不同，可计算性理论考虑的是“不惜一切代价”来解决。
复杂性理论在计算机中非常有用，如果以现有的算力，要运行1万年才能计算，那就是“不能计算”。
复杂性性理论有好几个图灵奖，比如1976年图灵奖（电台的第437期已经讲过），本期的史蒂芬·库克（1982年图灵奖）
关于计算理论目前还没讲的图灵奖还有好几位：卡普（1985年图灵奖）、1993年图灵奖、1995年图灵奖、2000年图灵奖（现在在清华大学的姚期智）、2002年图灵奖、2010年图灵奖、2012年图灵奖、2015年图灵奖、2023年图灵奖……
以后会慢慢讲。 https://youtu.be/BPReRBevufk?si=AYMLlg_AOI3vyWk-
最近江苏一个中专女生数学竞赛考了第12名，可以说是火遍全网了。但是，谁又懂她做的那些题呢？
恰好，本期的主人公，第17届图灵奖得主，也是数学家，搞计算复杂性理论的。这其实是一个数学分支，与普通人有一定的距离，具体来说，他是搞NP定理的。
对普通人来说，无关紧要。对科学家来说，至关重要。
计算复杂性理论可以确定一个问题能否被计算机以“合理的资源”求解。这跟可计算性理论不同，可计算性理论考虑的是“不惜一切代价”来解决。
复杂性理论在计算机中非常有用，如果以现有的算力，要运行1万年才能计算，那就是“不能计算”。
复杂性性理论有好几个图灵奖，比如1976年图灵奖（电台的第437期已经讲过），本期的史蒂芬·库克（1982年图灵奖）
关于计算理论目前还没讲的图灵奖还有好几位：卡普（1985年图灵奖）、1993年图灵奖、1995年图灵奖、2000年图灵奖（现在在清华大学的姚期智）、2002年图灵奖、2010年图灵奖、2012年图灵奖、2015年图灵奖、2023年图灵奖……
以后会慢慢讲。 https://youtu.be/BPReRBevufk?si=AYMLlg_AOI3vyWk-