[freddref]

We might not be able to avoid proof of work, but we could make the work useful in some other way.

Primecoin is an example of this, where the mining process produces prime numbers which can be useful for.. something?