[red75prime]

> if discovering the required technology to build a self-replicating interstellar probe requires solving an instance of an EXP problem[...]

Ah, I think I know why I felt it was very unlikely. Engineering constraints should be very "unlucky" so that only the solution works. That is, there's no wiggle room that allows an approximate solution (which is usually simpler to find) to work, even if it would be slightly heavier, costlier, or something of the sort.

For such a tight constraint not to be a coincidence, nature itself would have to be able to solve EXP problems. Which might mean that not all is lost.

ETA: ChatGPT has pointed out that many interesting instances of computationally hard problems are still solvable. For example, see SAT-solvers (SAT is NP-complete).

That is in addition to tight constraints the problem instance should have no exploitable structure.