Many bounded versions of undecidable problems are NP-hard
arXiv:2211.13532 · doi:10.21468/SciPostPhys.14.6.173
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.
arXiv comment10 pages and 7 pages of appendices, 8 figures; v2,v3: minor changes
References in corpus (17)
- Matrix Product Density Operators: Simulation of finite-T and dissipative systems
- Mixed-state dynamics in one-dimensional quantum lattice systems: a time-dependent superoperator renormalization algorithm
- Training variational quantum algorithms is NP-hard
- Undecidability of the Spectral Gap (short version)
- Unbounded number of channel uses are required to see quantum capacity
- Matrix product operators and states: NP-hardness and undecidability
- Tsirelson's problem and an embedding theorem for groups arising from non-local games
- Quantum measurement occurrence is undecidable
- Positivity of linear maps under tensor powers
- Fundamental limitations in the purifications of tensor networks
- Undecidability of the Spectral Gap in One Dimension
- Projected Entangled Pair States: Fundamental analytical and numerical limitations
- Quantum logic is undecidable
- Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy
- Translationally invariant universal classical Hamiltonians
- Halos and undecidability of tensor stable positive maps
- Undecidability in resource theory: can you tell theories apart?