Many bounded versions of undecidable problems are NP-hard
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 cor...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SciPost
2023-06-01
|
| Series: | SciPost Physics |
| Online Access: | https://scipost.org/SciPostPhys.14.6.173 |