> For instance, medieval times would likely be far easier to simulate than modern times,
Agreed.
> because the latter requires simulating our entire computer infrastructure.
Maybe, that isn't clear. There are probably plenty of optimisations here too if given some thought.
> I could use a solver on a big NP problem (we'll assume that P != NP), get a solution after an hour, and in theory, with some practice, I could probably check if the answer is correct in my head.
Yes, but note that we very rarely solve NP or EXPTIME problems exactly due to the costs. We often solve them heuristically or approximately, which wouldn't pose a problem for a simulation either.
Then there's also the possibility that we are simply not free to choose the problem to solve. When running a solver for an NP problem, we just need to input any kind of NP problem, and a simulation could easily have large sets of precomputed solutions available.
> Alternatively, the simulation could mess with our minds so we never notice anything out of place, but at that point I'm not sure I understand the point of it
Depends on whether any such changes affects the point of the simulation. If the simulation is to test world-scale economic models, then isolated tribes wouldn't have much influence on those outcomes.
Then again, maybe the point is simply entertainment. Maybe we're just The Sims for post-humans, in which case there's no point anyway.