Who ever said that the computer doing the simulation is working under laws of physics that are identical to our own? There are plenty of sets of physical laws that would support such a simulation, and a great many of them are entire computational complexity categories stronger than our own - consider, for example, a reality that is truly real-valued, rather than approximately real-valued with some semi-bounded probabilistic error. And then it's not "tiling some large fraction of reality" that's needed; if you go up a few alephs you end up with computers where our experienced reality falls out of people noodling and with stuff like "run all discrete programs with length less than N bytes" the same way we do things like compute the error of the fast inverse square root for all 32 bit floats.