什么是理论计算机科学?

主要观点:认为将理论计算机科学视为数学的分支对该学科有害,理论计算机科学应是“计算机科学和技术的形式基础研究”,不应是数学的分支,应从物理学中获取灵感,如计算复杂性理论虽优雅但未解释或预测 SAT 求解器的有效性。
关键信息:作者自认为是计算机科学家,被维基百科描述为“数学家和计算机科学家”, Avi Wigderson 对计算理论的定义较宽泛但其书范围较窄,20 世纪 80 年代 STOC 和 FOCS 范围变窄,TCS 社会学上不是数学分支,应从物理学获取灵感,计算复杂性理论中 NP 完全性概念虽优雅但未解释 SAT 求解器有效性等。
重要细节:作者 1993 年在 Rice 大学获计算机科学系教职,Avi 在数学系有主要职位;20 世纪 80 年代“卫星会议”出现导致 STOC 和 FOCS 范围变窄;计算复杂性理论聚焦根据资源使用分类计算问题等。

阅读 12
0 条评论