The low-value theoretical question is whether it's NP-hard. For something like SR, if the solution space were to be big enough such that potentially NP hardness

The low-value theoretical question is whether it's NP-hard. For something like SR, if the solution space were to be big enough such that potentially NP hardness would be a serious partical hurdle, it's extremely difficult to trust the outcome of solving the optimization problem. SR is equivalent to blind feature engineering. If I put it like that, probably most people who've done a bit of data science would know how bad of an idea it is unless we can regularize it well and bound the search space based on prior knowledge. Deep learning has the same theoretical problem and it's only overcome by its unreasonable empircal effectiveness on certain problems. And even then, nobody cares about its NP-hardness.