德克萨斯大学达拉斯分校的计算机科学教授声称已经证明了RP=NP

下载PDF摘要：我们(声称)证明了一个极其令人惊讶的事实：NP=RP。它是通过建立一个完全多项式时间随机近似方案(FPRAS)来实现的，它可以近似地计数有界度图中具有任何固定度界限的独立集的个数，这就意味着NP=RP。虽然我们的方法植根于著名的马尔可夫链蒙特卡罗(MCMC)方法，但我们通过从独立集合中生成随机样本的新思想克服了臭名昭著的缓慢混合问题。实现这一结果的一个关键工具是一种新的采样任务的解决方案，我们称之为子集采样。在它的基本形式中，从马尔可夫链的(指数大的)状态空间给出一个平稳样本作为输入，我们想把它转换成另一个平稳样本，该平稳样本的条件是落入一个仍然指数大的给定子集。一般来说，子集抽样比马尔可夫链上的平稳抽样既难又容易。这可能会更困难，因为子集的条件可能比原始状态空间具有更复杂的结构。但这也可能更容易，因为已经给出了一个固定样本，从某种意义上说，它已经包含了这类抽样任务的大部分难度，因为它已经处于平稳分布中，很难在缓慢的混合链中达到。我们证明了有效地平衡这两个方面是可能的：我们可以利用已经从原始空间获得的随机样本，从而减轻了将其限制在一个子集上的复杂性。我们证明了对于所考虑的采样任务，一个有效的近似是可能的，然后递归地应用它来创建FPRAS。