Suppose one has an algorithm for TSP or any other NP-complete problem. It can run in polynomial time if and only if a list of the first n primes are provided as precomputed. Would that be sufficient to prove P=NP?
My suspicion is no, my hope is yes.
For that matter, is there some algoithm that generates the nth prime deterministically in polynomial time or better, regardless of the size of n or at least up to very large n (10^22 maybe)?
Again, I suspect no.