How to Utilize Computing Power That is Now "Wasted" in Blockchain

As of the time I'm writing this, the Bitcoin network consumes more electricity than 159 of the countries in the world, as pointed out here.

To be clear - all this electricity is wasted by computers trying to solve (via brute-force) some computational problem. The first computer to solve it - is rewarded by the network, transactions are validated, another block is created, and everyone move on to the next problem. Another day on the blockchain.

And here's the somewhat weird part - nobody cares about the problems or the solutions. The only reason they are of interest, is that we can estimate the difficulty of solving them. So a huge amount of energy and resources is wasted on solving problems no one cares about.

Why Not Solve Important Problems Instead ?

I was thinking about this a few weeks ago when I thought - what if, instead of all this waste, those computers tried to solve hard problems that people do care about?
The famous class of NP-complete problems has a few problems in it that are real-world problems (other complexity classes make sense too, of course), for example - the traveling salesman problem (aka TSP). What if people who had TSP instances, because they are trying to navigate somewhere, or choose a route for some robot running erands in a large warehouse, could submit them to the blockchain and have them solved for them, using all this computing power?
There is an abundance of hard real-world computational problems, many of which arise in Chemistry and Biology. I understand very little about it, but I know researchers who actually send data to be processed for several days on a super-computer, just to get results for their research.
What if an entire blockchain network was, in effect, a crowd-sourcing project to solve hard computational problems? Wouldn't it be nice to put all this computing power to good use? Changing the existing Bitcoin protocol is probably out of the question at this point, but maybe a new crypto-coin, dedicated for that purpose? Maybe a different crypto-coin for different types of computational problems, the options are many, and seem interesting, at least in theory.

An illustration Google image search came up with for "hard computation"

The Nice Thing About This Idea

There are a few appealing notions here:

1. Hard problems are already sorted into complexity classes. This means that hard problems of the same class are convertible to one another. We can decide that the network actually solves 3SAT instances, and reduce any TSP instance to a 3SAT, and then submit it to the network.
2. It means hard problems actually have economic value for their hardness, where in the past it was only a cost associated with solving it. Now - solving the problem will oddly be its own reward... which is kind of neat.
3. Maybe when submitting a problem, one can offer a reward for solving it.

Some of The Problems

While being a nice idea, it has tons and tons of problems. Here are just a few

1. One can game the system - submit a problem, already knowing its solution, and collect the reward by solving it. This one is probably not hard to mitigate by scrambling the problem while converting it to the format readable by the network.
2. A harder issue is how do we know an instance is hard at all to begin with? There are SAT solvers in the world exactly because there are many heuristics that cover some types of instances of the problem.
3. Do people really need exact solvers? At least for the case of NP problems - for many of them an approximated solution is good enough, so is this really filling a need that people actually have? I don't know.

There are probably many other issues with this idea, but I thought it would be nice to put it out there.

P.S.

The world is a big place, I will be very surprised if I'm the first to come up with this...