高中数学127个快速解题公式七大数学难题( 四 ) _数学

世界七大数学难题：
1、P/NP问题（PNP）
2、霍奇猜想（The Hodge ）
3、庞加莱猜想（The é ），此猜想已获得证实。
4、黎曼猜想（The）
5、杨-米尔斯存在性与质量间隙（Yang-Millsand Mass Gap）
6、纳维-斯托克斯存在性与光滑性（-and ）
7、贝赫和斯维讷通-戴尔猜想（The Birch and -Dyer ）
所谓的世界七大数学难题其实是于2000年5月24日由由美国克雷数学研究所公布的七个数学难题。也被称为千禧年大奖难题。根据克雷数学研究所订定的规则，所有难题的解答必须发表在数学期刊上，并经过各方验证，只要通过两年验证期，每解破一题的解答者，会颁发奖金100万美元。这些难题是呼应1900年德国数学家大卫·希尔伯特在巴黎提出的23个历史性数学难题，经过一百年，许多难题已获得解答。而千禧年大奖难题的破解，极有可能为密码学以及航天、通讯等领域带来突破性进展。
一：P/NP问题
P/NP问题是世界上最难的数学题之一。在理论信息学中计算复杂度理论领域里至今没有解决的问题，它也是克雷数学研究所七个千禧年大奖难题之一。P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克和 Levin相对独立的提出了下面的问题，即是否两个复杂度类P和NP是恒等的（P=NP?）。复杂度类P即为所有可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所有可以在多项式时间内验证解是否正确的决定问题组成，或者等效的说，那些解可以在非确定型图灵机上在多项式时间内找出的问题的集合。很可能，计算理论最大的未解决问题就是关于这两类的关系的： P和NP相等吗？在2002年对于100研究者的调查， 61人相信答案是否定的， 9个相信答案是肯定的， 22个不确定，而8个相信该问题可能和现在所接受的公理独立，所以不可能证明或证否。对于正确的解答，有一个1百万美元的奖励。NP-完全问题（或者叫NPC）的集合在这个讨论中有重大作用，它们可以大致的被描述为那些在NP中最不像在P中的（确切定义细节请参看NP-完全理论）。计算机科学家现在相信P, NP ，和NPC类之间的关系如图中所示，其中P和NPC类不交。
假设P ≠ NP的复杂度类的图解。如P = NP则三个类相同。简单来说， P = NP问题问道：如果是／不是问题的正面答案可以很快验证，其答案是否也可以很快计算？这里有一个给你找点这个问题的感觉的例子。给定一个大数Y ，我们可以问Y是否是复合数。例如，我们可能问是否有非平凡的因数。答案是肯定的，虽然手工找出一个因数很麻烦。从另一个方面讲，如果有人声称答案是"对，因为可以整除" ，则我们可以很快用一个除法来验证。验证一个数是除数比找出一个明显除数来简单得多。用于验证一个正面答案所需的信息也称为证明。所以我们的结论是，给定正确的证明，问题的正面答案可以很快地（也就是，在多项式时间内）验证，而这就是这个问题属于NP的原因。虽然这个特定的问题，最近被证明为也在P类中（参看下面的关于"质数在P中"的参考），这一点也不明显，而且有很多类似的问题相信不属于类P 。像上面这样，把问题限制到“是／不是”问题并没有改变原问题（即没有降低难度）；即使我们允许更复杂的答案，最后的问题（是否FP = FNP）是等价的。

高中数学127个快速解题公式 七大数学难题( 四 )

高中数学127个快速解题公式七大数学难题( 四 )