[red75prime]

> there is no reason to believe that the way to build it would be found before, say, the sun runs out of hydrogen.

A lot of computational power can be thrown at the problem in this time. So, the problem should admits no shortcuts, no decomposition into simpler problems, no alternative ways to get similar functionality that allow shotrcuts or decomposition. The result should look like a jumble of atoms that somehow produces the required functionality.

I wonder which problems can admit only this kind of a solution.

[simiones]

> A lot of computational power can be thrown at the problem in this time.

We know plenty of actually very simple problems that we would not be able to solve from now till the Sun explodes even if we all of the computers on earth were only doing this. Say, solving a worse case instance of the Knapsack problem for n > 250 items easily fits into this.

If you want to be precise, the complexity class EXP best fits my description (though NP-complete would also be enough). That is, if discovering the required technology to build a self-replicating interstellar probe requires solving an instance of an EXP problem that is not ridiculously tiny, then we would likely never be find out how to build this probe. And no amount of AGI would change this, in this case.

I'm not suggesting that I have any reason for this ridiculously precise scenario to be correct. Just that some technology being allowed by the laws of physics should not be taken to mean that it is actually implementable in any imaginable amount of time, even if we were to assume singularity-style AGI.

[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.