Scott Aaronson wrote a great paper arguing around what you mentioned[1]. He tackles the issue of why a waterfall does not simulate a universe if we transform the waterfall in an appropriate way. He argues that the waterfall would indeed simulate a universe, if and only if the transformation function is of polynomial complexity. However! He argues that it is more likely such a transformation is if exponential complexity, or of an even higher order, and thus the waterfall does not simulate a universe. A polynomial transformation function to turn a grain of sand into a universe existing seems like quite a strong assumption.
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.
Interesting point! All I have to bring in is that if computational complexity is of no interest to inhabitants of a simulation, very strong assumptions about the nature of the simulating universe still need to be made? This, I think, means that you're saying that time is for all intents and purposes unbounded/unlimited/infinite in the simulating universe. As the law of physics that turns exp->poly problems would still need to be simulated, and likely, if i understand correctly, is not necessarily polynomial in the simulating universe?
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