Ah, I think we have a deep "philosophy of science" disagreement. Basically, it is not just "falsifiability", but also "probability" of being correct. Probability that can be informed by things like formal versions of Occam's razor (e.g. Kolmogorov complexity, Akaike information criterion, etc).
Here are a few premises on which I based my statement (I will pick one particular venue of scientific research, so I will not speak in all generality. You can of course disagree and say that it does not generalize at all, but I think this would be a philosophical discussion, i.e. it does not matter at all that we have different opinions, as both are equally valid ways of pursuing scientific truth):
1. Computational complexity is a science on its own. Computational complexity also makes useful statements about the limits of the physical laws in our universe (a la "extended Church-Turing thesis" or Aaronsons "NP-complete problems and physical reality").
2. NP=P vs NP!=P is a question that has a definite answer within the relm of science but we do not know the answer yet. The answer will constrain what the permitted laws of physics are due to point 1 above.
3. There are a lot of clues that NP!=P coming from very separate disjoint fields of math. Mainly because we already know there are a lot of "phase transition"-like phenomena when we apply approximate algorithms to problems that can be parameterized to be NP-complete only if some ε is larger than some critical value.
4. These "phase transitions" are purely mathematical constructs, but due to the previous points they constrain what is permitted in the universe as strongly as any 5-sigma measurement in a particle accelerator.
To bring this back to the discussion of speculative theories of quantum gravity: if all of the competing theories of quantum gravity (all of them being very speculative and unproven) have a handful universally agreed on predictions (although derived in completely separate ways), this is as strong of a constraint as any 5-sigma measurement in a particle accelerator or cosmological observation.
Or if you permit me to attempt to phrase is it in yet another way: there are a ton of theory assumption behind any 5-sigma (or 10-sigma) experimental measurement. These assumptions are the same ones that inform the purely mathematical constraints. If both the math constraints and the interpretation of an experiment are based on the same assumption, why are you taking the interpretation of the experiment any more seriously than the pure math.
Sorry for the length of this text - I am finishing my dissertation this week (doctorate in physics), so this is very much on my mind at the moment.