The described proof-of-work system is known as hashcash http://www.hashcash.org/docs/hashcash.html http://www.hashcash.org/docs/hashcash.html which asks for a p

The described proof-of-work system is known as hashcash http://www.hashcash.org/docs/hashcash.html http://www.hashcash.org/docs/hashcash.html which asks for a partial preimage of a hash function. There are indeed other proof-of-work algorithms. Probably the first one is Primecoin, which asks for a Cunningham chain of prime-numbers. My own Cuckoo Cycle, asking for a cycle in a huge graph, is another example, in which a single proof attempt takes hundreds of MB of memory, but verification is instant and takes no memory.