论文标题
许多不确定问题的有界版本是NP-HARD
Many bounded versions of undecidable problems are NP-hard
论文作者
论文摘要
事实证明，有几个受身体启发的问题是不可决定的。示例是光谱差距问题和量子相关性的成员资格问题。这些结果中的大多数都取决于少数无法确定的问题的减少，例如停止问题，平铺问题，后通信问题或矩阵死亡率问题。所有这些问题都有一个共同的属性：它们具有NP-HARD有限的版本。这项工作建立了无法确定的无界问题与其有限的NP-HARD版本之间的关系。具体而言，我们表明，有界版本的NP硬度可以轻松地遵循无限问题的减少。这导致了有关邮政对应问题有限版本的NP硬度，矩阵死亡率问题，矩阵产品运营商的积极性，可及性问题，平铺问题和基态能量问题的新的简单证明。这项工作阐明了问题在理论物理学和界限参数的计算后果中的可行性。
Several physically inspired problems have been proven undecidable; examples are the spectral gap problem and the membership problem for quantum correlations. Most of these results rely on reductions from a handful of undecidable problems, such as the halting problem, the tiling problem, the Post correspondence problem or the matrix mortality problem. All these problems have a common property: they have an NP-hard bounded version. This work establishes a relation between undecidable unbounded problems and their bounded NP-hard versions. Specifically, we show that NP-hardness of a bounded version follows easily from the reduction of the unbounded problems. This leads to new and simpler proofs of the NP-hardness of bounded version of the Post correspondence problem, the matrix mortality problem, the positivity of matrix product operators, the reachability problem, the tiling problem, and the ground state energy problem. This work sheds light on the intractability of problems in theoretical physics and on the computational consequences of bounding a parameter.
