That SR is NP-hard seems pretty trivial to me. Especially since the problem is framed to be combinatorial in nature; with a sufficiently weird family of functions, you'll be able to find an NP-hard class of subproblems.

The computationally difficulty of something like SR is also deeply connected to its applicability. If you have data where it's easy to apply SR and trust it, it tends to be easy; to trust your ability more you probably want to add regularization based on the complexity of the final formula, and probably you'd have strong priors on a small set of functions that are applicable. Once you don't have this, and get to where the problem can be plausibly NP-hard, you're going to overfit and the technique is worthless.

There's a family of ML theoretical questions that are just very low value as they make very little progress in helping to understand important problems. This is one of them.