A deterministic universe might not be a quantum universe, in which case algorithms like Shor's algorithm would be impossible; whether there will be a quantum or post-quantum method for solving NP problems in P-time is unknown. Suppose that there is. This won't mean that P = NP; Shor's algorithm is in complexity class BQP: bounded error quantum polynomial time.
The NP complexity class is a different kind of non-deterministic than our current knowledge of quantum mechanics and its non-deterministic nature. We know this because no known quantum computer can solve NP-complete problems in polynomial time. This is because to solve NP-complete problems in P-time, you would need to be able to spawn n – 1 new instances of the program at every decision point with n possible decisions. It's not quite "trying everything simultaneously", but it's close. No known quantum computer can "try everything at once"; this is because quantum circuits aren't 'powerful enough'.
Suppose that we find a new kind of quantum computer that can solve NP-complete problems in P-time. Whether or not the universe had to be this way will probably be a matter for philosophers. But surely you can see that in a deterministic universe, that quantum computer [probably] wouldn't be available. So if you create a digital world populated by sentient beings and make that world deterministic, those beings probably won't be able to compute as much as you can in any given time period.
All this being said, it could turn out that classical computers can be used to solve NP problems in P-time, if it ends up that P = NP. In that case, whether or not the world is deterministic or indeterministic would be utterly irrelevant. At this point, we just don't know. If you want your mind blown with respect to computation and physics, see this primer on black hole computation, and then head over to Scott Aaronson's discussion of recent firewall controversies. "What is realistically computable in our universe?" is a fascinating question. Maybe there is a deep link between computation and physics!