#子集

德克萨斯大学达拉斯分校的计算机科学教授声称已经证明了RP=NP
UT Dallas Computer Science professor claims to have proven RP = NP(arxiv.org)
2020-8-5 4:36
下载PDF摘要：我们(声称)证明了一个极其令人惊讶的事实：NP=RP。它是通过建立一个完全多项式时间随机近似方案(FPRAS)来实现的，它可以近似地计数有界度图中具有任何固定度界限的独立集的个数，这就意味着NP=RP。虽然我们的方法植根于著名的马尔可夫链蒙特卡罗(MCMC)方法，但我们通过从独立集合中生成随机样本的新......