#rp

下载PDF摘要：我们(声称)证明了一个极其令人惊讶的事实：NP=RP。它是通过建立一个完全多项式时间随机近似方案(FPRAS)来实现的，它可以近似地计数有界度图中具有任何固定度界限的独立集的个数，这就意味着NP=RP。虽然我们的方法植根于著名的马尔可夫链蒙特卡罗(MCMC)方法，但我们通过从独立集合中生成随机样本的新......