SciPost Submission Page
Many bounded versions of undecidable problems are NP-hard
by Andreas Klingler, Mirte van der Eyden, Sebastian Stengele, Tobias Reinhart, Gemma De las Cuevas
This Submission thread is now published as
Submission summary
| Authors (as registered SciPost users): | Andreas Klingler · Sebastian Stengele |
| Submission information | |
|---|---|
| Preprint Link: | https://arxiv.org/abs/2211.13532v3 (pdf) |
| Date accepted: | 2023-04-18 |
| Date submitted: | 2023-03-16 11:14 |
| Submitted by: | Klingler, Andreas |
| Submitted to: | SciPost Physics |
| Ontological classification | |
|---|---|
| Academic field: | Physics |
| Specialties: |
|
| Approaches: | Theoretical, Computational |
Abstract
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.
Author comments upon resubmission
List of changes
1. Following the suggestion of both referees, we clarified in Section 2 that there is, to the best of our knowledge, no prior work on bounding from a systematic perspective.
2. Following the suggestion in Report 1, we added a discussion about whether a converse statement to the main theorem also holds. This includes a comment on unbounding in Section 2 and a new paragraph in Section 5.
3. Following Report 1, we clarified why p needs to be strictly increasing in Theorem 2. Moreover, we weakened the assumption in Equation (1).
4. We restructured the presentation of the examples HALT, NHALT, and NHALTAll. Specifically, we removed NHALT as an example of bounding in Section 2 and directly introduced it as a root problem in Section 3. Moreover, we added a paragraph in Section 3 that clarifies that the deterministic Halting problem HALT is too weak to act as a root problem.
5. We changed the caption in Figure 2 to explain every abbreviation in the figure.
6. Following Report 2, we added a paragraph in Section 4.C clarifying the use of diagonal MPOs instead of the general definition.
7. Following Report 2, we added the approximate MPO problem and its bounded version as an example highlighting that our theorem can be used for problems containing approximation errors.
8. Following Report 2, we added a paragraph in Section 4.G. to explain why it is necessary to use NHALTAll instead of NHALT as a root problem for the Wang tiling problem.
9. Following Report 1, we elaborate on the definition of coNP in Appendix A.c and clarify its use when proving the completeness of BNHALTAll.
Published as SciPost Phys. 14, 173 (2023)