Another point I'd add is that we've already got practical examples of computations that are especially hard for computers to practically do even if they are "obvious" in theory — we use those as a base for encryption, for instance.