But, what if there's a law of physics inside of the simulated universe that solves exponential problems in polynomial time? You could pack a more limited universe inside of that one, if you didn't want your inhabitants to have access to it. I think that computational complexity absolutely does determine how useful a simulation is to us, but it's not meta-universal enough to do this kind of philosophy with.
If I'm interpreting it correctly it does seem to put some constraints on the nature of the simulating universe, but does not necessarily disprove the existence of it?
We can divide up the task of running a physical simulation into the part where the state is computed, and the part where the results are made visible to us in a way we understand.
We can also divide computation up into the same two pieces: the actual solving of the problem, and then the task of reading symbols off the Turing tape. Usually, we set up our definitions so that a program isn't thought to "solve" a problem unless the reading-the-answer part is trivial.
Now, for a person living inside a simulation, the reading-the-answer part would become insignificant. Why do they care if we can see in to their universe?
So, if all we want is to make a world for simulated people to live in, why not stuff all of the computational complexity into the reading-the-answer part, and then not do it? They would be perfectly happy with a jumbled-up, uninterpretable state in our world, because they would be living on the inside where it made sense.
So, if that is convincing, then allow me to pitch my universe simulating computer:
Launch two photons into space. The distance between them is the state of the simulation. If you want to look in to the state, you have to solve an incredibly hard exponential problem to map the distance to a certain corresponding wavefunction that you could make sense out of.
However, the inhabitants wouldn't care about whether or not you interpreted their state. So, as far as the simulated are concerned, two photons flying apart do make a simulation!
In my opinion the easiest way to make this reductio-ad-absurdum go away is to reject the idea that the simulated is real.
[1] https://www.scottaaronson.com/papers/philos.pdf