Bram writes about partial busy-work functions. I need to know more about the requirements for generation and verification before I can see how to attack it. The only requirements I have are these:

• There is a graph with n nodes
• Each node is associated with a puzzle, and there's a puzzle for the whole graph
• Each node puzzle should take k work to solve
• The whole graph puzzle is easy to solve if you have the solution for any two nodes on the same arc.
• The solution is the same no matter which arc you use.

I can see several trivial solutions, but they have these disavantages: it takes as much work to verify a solution ans it does to generate it, and generating all the puzzles takes nk time. Usually you want a busy-work puzzle to be trivial to generate and verify, eg "find a 160-bit value that hashes to something with the prefix 72f3ab81". Bram, what are your reqirements with this?

Bayes and scoring

I've got a better grasp on what these probabilities really mean, and why (as I wrote last time) (a o_s b) = (a o b o (1-s)). If anyone's reading, mail me, I'd be happy to write it up...