full
search.png

Search

close.png

Cancel

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

尼 克

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

查看节选 购买查看 529 40936
  • 摘要


image.png

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