SciPost Submission Page
Many bounded versions of undecidable problems are NPhard
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:  20230418 
Date submitted:  20230316 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 NPhard bounded version. This work establishes a relation between undecidable unbounded problems and their bounded NPhard versions. Specifically, we show that NPhardness of a bounded version follows easily from the reduction of the unbounded problems. This leads to new and simpler proofs of the NPhardness 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)