Solving the crypto problem is just part of the mechanism that ensures there's a limited supply of them. We could do the same thing by randomly assigning floating point numbers between 0 and 2.1x10^10 - 1 (corresponding to the 21M BTC that are ever allowed to exist).

The part that makes BTC relatively safe to transact with is the blockchain itself.