计算复杂性50年：王浩与计算理论

摘要

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