This question was discussed at http://stackoverflow.com/questions/806569/whats-the-opposite-of-embarrassing... The most interest example was: The number of women will not reduce the length of pregnancy. On Mon, Aug 4, 2014 at 10:09 PM, Henry Baker <hbaker1@pipeline.com> wrote:
If there are any computational complexity theorists out there, I was wondering if there were any examples of "essentially serial" computations, in which no amount of parallelism (and no amount of memory) can speed it up. I.e., the only speedup comes from a faster CPU clock.
Obviously, one can use a Turing Machine to "diagonalize" over all Turing Machines with smaller time & space, but this doesn't say much about access to huge amounts of parallelism.
The goal is a Bitcoin-type "proof of work" in which buying more computers won't help at all; hopefully the speedup of special hardware over a random laptop or cellphone would be perhaps 3 orders of magnitude, but not more.
Any links/pointers would be welcomed.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun