我在哪里可以找到数字符号问题是 NP-hard 的证据?

计算科学 参考请求
2021-12-04 18:03:07

我已经阅读了数字符号问题,以及通用解决方案如何是 NP-Hard。不过,我似乎找不到这方面的证据。

有谁知道我在哪里可以找到数字符号问题是 NP-Hard 的证据?

1个回答

据称,论文中提供了一个证明:“费米子量子蒙特卡罗模拟的计算复杂性和基本限制”。单击此处获取 arXiv 链接这是摘要:

量子蒙特卡罗模拟虽然对玻色子很有效,但在应用于费米子时会遇到“负号问题”——导致计算时间随粒子数量呈指数增长。非常需要符号问题的多项式时间解因为它将提供一种无偏且数值精确的方法来模拟相关的量子系统。这里我们证明,通过证明符号问题是 NP 难的,几乎可以肯定这样的解决方案是无法实现的,这意味着符号问题的通用解决方案也将在多项式时间内解决复杂性类 NP(非确定性多项式)中的所有问题。

显然,统计力学领域的人比我更熟悉这一点。物理 StackExchange 上的这篇文章也讨论了符号问题——这里也是