The mining algorithm for Bitcoins (and most alternative but similar currencies as well) is purely computation hard, but not decision hard or memory hard. This caused the unexpected effect that GPUs are insanely good at mining and CPUs are so bad at mining that there's almost no point in using them to mine.
This has had many effects, including the concentration of mining into specialized hardware. Suppose that I think that's bad and would prefer that commodity CPUs be optimal for mining and that mining on them be practical. Given the requirements of mining, particularly that it work like a lottery and that valid results be quickly verifiable, are there algorithms that could have been chosen that would have resulted in commodity CPUs being the optimal miners?
Are there algorithms that require lots of decisions and/or lots of memory that could serve as the mining algorithm on future crypto-currencies that would make CPU mining practical again and give everyone with a high-end CPU a reasonable chance at mining?