世界上最难的数学题(2)

假设PNP的复杂度类的图解。如P = NP则三个类相同。 简单来说，P = NP问题问道：如果是／不是问题的正面答案可以很快验证，其答案是否也可以很快计算？这里有一个给你找点这个问题的感觉的例子。给定一个大数Y，我们可以问Y是否是复合数。例如，我们可能问53308290611是否有非平凡的因数。答案是肯定的，虽然手工找出一个因数很麻烦。从另一个方面讲，如果有人声称答案是对，因为224737可以整除53308290611，则我们可以很快用一个除法来验证。验证一个数是除数比找出一个明显除数来简单得多。用于验证一个正面答案所需的信息也称为证明。所以我们的结论是，给定正确的证明，问题的正面答案可以很快地（也就是，在多项式时间内）验证，而这就是这个问题属于NP的原因。虽然这个特定的问题，最近被证明为也在P类中（参看下面的关于质数在P中的参考），这一点也不明显，而且有很多类似的问题相信不属于类P。
像上面这样，把问题限制到是／不是问题并没有改变原问题（即没有降低难度）；即使我们允许更复杂的答案，最后的问题（是否FP = FNP）是等价的。
关于证明的难度的结果

虽然百万美元的奖金和投入巨大却没有实质性结果的大量研究足以显示该问题是困难的，但是还有一些形式化的结果证明为什么该问题可能很难解决。 最常被引用的结果之一是设计神谕。假想你有一个魔法机器可以解决单个问题，例如判定一个给定的数是否为质数，可以瞬间解决这个问题。我们的新问题是，若我们被允许任意利用这个机器，是否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题？结果是，依赖于机器能解决的问题，P = NP和PNP二者都可以证明。这个结论带来的后果是，任何可以通过修改神谕来证明该机器的存在性的结果不能解决问题。不幸的是，几乎所有经典的方法和大部分已知的方法可以这样修改（我们称它们在相对化）。 如果这还不算太糟的话，1993年Razborov和Rudich证明的一个结果表明，给定一个特定的可信的假设，在某种意义下自然的证明不能解决P = NP问题。
这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类定理得到证明，该定理的可能证明方法有越来越多的陷阱要规避。 这实际上也是为什么NP完全问题有用的原因：若对于NP完全问题存在有一个多项式时间算法，或者没有一个这样的算法，这将能用一种相信不被上述结果排除在外的方法来解决P = NP问题。
二、霍奇猜想

霍奇猜想是代数几何的一个重大的悬而未决的问题。它是关于非奇异复代数簇的代数拓扑和它由定义子簇的多项式方程所表述的几何的关联的猜想。它在霍奇的著述的一个结果中出现，他在1930至1940年间通过包含额外的结构丰富了德拉姆上同调的表述，这种结构出现于代数簇的情况（但不仅限于这种情况）。
三、庞加莱猜想