主题不存在 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

Programming版 - Kevin Buzzard：计算机做不到什么？ https://www.youtube.com/watch?v=jQPb7DRMoZY&list=FL3RezzS-A7eu0NV9aDxzpdA&i

(共1页)

w**********5
发帖数: 1741

Kevin Buzzard：计算机做不到什么？
https://www.youtube.com/watch?v=jQPb7DRMoZY&list=FL3RezzS-A7eu0NV9aDxzpdA&
index=55&t=0s 人们最早开始关心计算机完成某事的速度而不仅仅是抽象的计算机能否
完成某事是在1955年，相关记录是一封信，发信人是《美丽心灵》的主人公约翰.纳什
，收信人是美国国家安全局。他在信中指出，关键不在于计算机能否解决某个问题，而
是在于计算机解决这个问题的速度。按照纳什的说法，假如某个计算机程序能在多项式
时间内运行，那么这个程序在数据缩放方面就像程序一。当然这种说法并不规范。规范
说法是：假如某程序的功能可以用多项式函数P(n)来表达，那么这个程序就可以在多项
式时间内运行。..数学家将所有能够被计算机迅速解决的问题统称为P。..NP指的是一
切能够快速验算——也就是在多项式时间内验算——的问题的集合。所以说，P是一切
能够快速计算的问题，NP是一切可以快速检验答案对错的问题。如果一个问题属于P，
那也一定属于NP。但是很多属于NP的问题我们却无法快速解答. 接下来的问题是：P是
否等于NP呢？如果某个问题我们能够快速验算，那么是否也能快速计算呢？1971年，斯
蒂芬.库克率先提出了这个问题。他对这个问题进行了严格的数学定义，为后来的研究
打下了基础。不过这一年他没能得到伯克利大学的终身教职，因为当时计算机领域实在
无关紧要。如今这个问题却成为了克雷数学研究所的七个千年大奖问题之一，企业界为
每个问题都设置了百万美元的奖金

(共1页)

进入Programming版参与讨论

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天