Moreover, no one really knows how hard it is to compute a valid block. The trial-and-error method used by miners is just the most efficient method that we know; but there is no proof or other evidence that there is no better way.
Would you consider the fact that nobody has ever found a collision of sha256 function an evidence? There's no mathematical proof, but there's more then enough evidence that any other method is not even on the horizon. It's not only a Bitcoin issue, if any of modern hash algorithms would be compromised the whole cryptography would be hammered.