Also, they must be a lottery, in that it's lots of "easy" problems that have a small chance. Otherwise it weakens the "50% attack" by meaning that someone with the most computing power can efficiently "hard" problem much more reliably, rather than the their percentage of the total computing power.