Naturally solved problems that are easy to verify but that would be hard to compute

To expand on this: in this paper, Scott Aaronson points out, it's quite hard to find a problem which looks like it is computing anything interestingly hard aside from quantum effects

Yes. OTOH, quantum effects don't seem to provide a general solution for 'easily-checkable' problems (beyond the modest improvement that Grover's algorithm brings to black-box search). However, closed timelike curves would provide easy solutions for any problem in PSPACE, which does include NP.

For Bostrom's simulation argument to conclude the disjunction of the two interesting propositions (our doom, or we're sims), you need to assume there are simulation runners who are motivated to do very large numbers of ancestor simulations. The simulation runners would be ultrapowerful, probably rich, amoral history/anthropology nerds, because all the other ultrapowerful amoral beings have more interesting things to occupy themselves with.

While Bostrom's argument as originally stated does reference specifically ancestor studies, here Bostrom says:

More generally, simulators might create many simulated people who are very different from their own ancestors, or who live in worlds that are very different from the one that the simulators live in. It is possible that we are living in such a simulation. I don't know of any way of estimating the probability that our hypothetical simulators (or their ancestors) are similar to us, or that their world is similar to the world we experience. (The original paper focuses on ancestor-simulations because the methodology is more solid for that case. It is less clear whether some kind of principle of indifference could also be applied to a reference class of "observer-moments" that are very different from one another...).

So, I think that the simulation argument could be generalized to refer to "civilization simulations" in lieu of "ancestor simulations". If so, there is no reason to assume that the simulation runners would necessarily be history/anthropology nerds. In fact, there could be any number of reasons why running a civilization simulation could be useful or interesting.

Companies writing programs to model and display large 3D environments in real time face a similar problem, where they only have limited resources. One work around they common use are "imposters"

A solar system sized simulation of a civilisation that has not made observable changes to anything outside our own solar system could take a lot of short cuts when generating the photons that arrive from outside. In particular, until a telescope or camera of particular resolution has been invented, would they need to bother generating thousands of years of such photons in more detail than could be captured by devices yet present?

If it is the case that we are in a "perfect" simulation, I would consider that no different than being in a non-simulation. The concept of being "in a simulation" is useful only insofar as it predicts some future observation. Given the various multiverses that are likely to exist, any perfect simulation an agent might run is probably just duplicating a naturally-occurring mathematical object which, depending on your definitions, already "exists" in baseline reality.

The key question, then, is not whether some simulation of us exists (nearly guaranteed) but how likely we are to encounter an imperfection or interference that would differentiate the simulation from the stand-alone "perfect" universe. Once that happens, we are tied in to the world one level up and should be able to interact with it.

There's not much evidence about the likelihood of a simulation being imperfect. Maybe imperfect simulations are more common than perfect ones because they're more computationally tractable, but that's not a lot to go on.