第十三卷, 第一期
计算复杂性50年:王浩与计算理论

尼 克

数学文化, 13 (2022), pp. 25-35.

查看节选 购买查看 28 21139
  • 摘要


image.png

如果说图灵1936年那篇开天辟地的文章奠定了计算理论的基础,那么说库克(Stephen Cook)1971年的文章《定理证明过程的复杂性》是计算复杂性的开山之作,一点也不夸张。从库克文章发表日开始算,计算复杂性理论50岁了(2021年)。2021年又是库克的导师王浩冥诞100年。本文回溯计算复杂性的起源,并力图梳理王浩和这门学科的关系。