Automatizing rewards for solving hard problems with Bitcoin
blogchain.fr
blogchain.fr
As for using blockchain directly for contract - there are a few addresses that have funds locked for the first person to find collisions in sha1, sha256 and others: https://bitcointalk.org/index.php?topic=293382.0
Finally, there's (or "there will be") Ethereum which seems best for preparing contracts that require no external inputs. Solving hard problems usually requires no such inputs.
As for Ethereum, I know that it is the goal, certainly the fact that it is Turing-complete argues in favor of this usecase. However, how practical and efficient is it, as in what kind of slowdown in the execution would you get on the blockchain?