Some people think that complexity issues are even more fundamental than the laws of physics.
Sure. And I'm probably one of the people here who is most vocal about computational complexity issues limiting what recursive self-improvement can do. But even then, I don't see them as necessarily in the same category. Keep in mind, {L, P, NP, co-NP, PSPACE, EXP} being all distinct are conjectural claims. We can't even prove that L != NP at this point. And in order for this to produce barriers to recursive self-improvement one would likely need even stronger claims.
The same people who are very skeptical in the case of faster than light neutrinos just make up completely unfounded probability estimates about the risks associated with recursive self-improvement because it is easy to do so, because there is no evidence either way.
Well, but that's not an unreasonable position. If I don't have strong evidence either way on a question I should move my estimates close to 50%, That's in contrast to the FTL issue where we have about a hundred years worth of evidence all going in one direction, and that evidence includes other observations involving neutrinos.
SN_1987 shows that neutrinos travel at the speed of light almost all of the time but does not rule out that they might have velocities that exceed that of light very briefly at the moment they're generated. See here for more. Note that I, like the author of the post I've linked, do not believe that this finding will stand up. It's just that if it does stand up, it will be because the constant velocity assumption is wrong.
Link: nextbigfuture.com/2011/11/faster-than-light-neutrinos-opera.html
Link: science20.com/quantum_diaries_survivor/opera_confirms_neutrinos_travel_faster_light-84763
Paper: kruel.co/paper-neutrino-velocity-JHEP.pdf
Previously on LW: lesswrong.com/lw/7rc/particles_break_lightspeed_limit/