Consider the following simple technique for
combatting junk mail (spam):
If I don't know you, and you want your e-mail to
appear in my inbox,
then you must attach to your message an easily
verified "proof of computational effort"
just for me and just for this message.
To apply this approach one needs to be able to come up with computational problems where solving them requires significant expenditure of resources while verifying a solution can be done easily. The papers below introduce this approach (see here) and concentrate on the choice of computational problems for which most of the work is in retrieving information from memory (see here). In particular the connection to pebbling problems is described here. Finally, for a survey on moderate hardness see here.
On-Line
Papers: