千禧年大奖难题

美国克雷数学研究所公布的猜想
千禧年大奖难题(Millennium Prize Problems), 又称世界七大数学难题,是七个由美国克雷数学研究所(Clay Mathematics Institute,CMI) 于2000年5月24日公布的数学猜想。拟定这7个问题的数学家之一是怀尔斯费马大定理这个有300多年历史的难题没被选入的唯一理由就是已经被他解决了。其他的专家,除了克雷促进会会长贾菲(Arthur Jaffe),还有阿蒂亚和在巴黎演讲的泰特,以及法国的孔涅(Alain Connes)和美国威滕(Edward Witten)。根据克雷数学研究所订定的规则,任何一个猜想的解答,只要发表在数学期刊上,并经过两年的验证期,解决者就会被颁发一百万美元奖金。它们分别是NP完全问题、霍奇猜想庞加莱猜想、黎曼假设、杨-米尔斯存在性和质量缺口、纳卫尔-斯托可方程、BSD猜想。其中庞加莱猜想已被解决。这些难题是呼应1900年德国数学家大卫·希尔伯特在巴黎提出的23个数学问题。

P等于NP

千禧年大奖难题
千禧年大奖难题
主条目:P/NP问题
尽管计算机极大地提高了人类的计算能力,仍有各种复杂的组合类或其它问题随规模的增大其复杂度也快速增大,通常我们认为计算机可以解决的问题只限于多项式时间内,即所需时间最多是问题规模的多项式函数.