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

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

Year:    2022

Author:    尼 克

数学文化, Vol. 13 (2022), Iss. 1 : pp. 25–35

Abstract


image.png

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

You do not have full access to this article.

Already a Subscriber? Sign in as an individual or via your institution

Journal Article Details

Publisher Name:    Global Science Press

Language:    Chinese

DOI:    https://doi.org/2022-MC-20333

数学文化, Vol. 13 (2022), Iss. 1 : pp. 25–35

Published online:    2022-01

AMS Subject Headings:   

Copyright:    COPYRIGHT: © Global Science Press

Pages:    11

Keywords:   

Author Details

尼 克