News
Positivity of Matrix Moments
In this paper, we examine the moment membership problem, investigating both its decidability and undecidability.
Many bounded versions of undecidable problems are NP-hard
Being undecidable and NP-hard are two ways of being hard - the former for machines with unbounded time, the latter for machines with poly-bounded time.
Does bounding an undecidable problem result in an NP-hard problem? Quite often. SciPost Phys. 14, 173 (2023)