At end of the earlier thread re bitcoin, I had discussed this question a little. I'd argued that what was wanted was not only that the problem be "essentially serial" but also that it be in NP U co-NP so that you could rapidly prove that you'd done the work, without somebody else having to redo the entire computation in order to believe you (i.e. verification is in P, much faster than finding the proof, which is not in P). Let's take it for granted that P is a *strict* subset of NP U co-NP, since fat chance anybody will be able to prove that. I'd suggested, in what I said at the time was probably a bad suggestion, the same thing Adam Goucher just suggested -- integer factorization. However, the reason this is a bad suggestion, is that the best factorization methods for larger integers (GNFS, quadratic sieve, etc) are very highly parallelizable, in fact that is the only way they've been able to factor large numbers at all. QUESTION: What problems, if any, lie in NP U co-NP, but outside P, and furthermore seem inherently unparallelizable? And the point by Cris Moore about "P-complete" problems being unparallelizable is ok per se, BUT a bad idea for our purpose, because those are in P. We want problems outside of P for proof of work purposes, otherwise the work is too easy. Thing is, I just now thought of an argument that THIS QUESTION HAS NO ANSWER. That is because ANY problem that can be verified in P, but cannot be solved in P, AUTOMATICALLY seems highly parallelizable to solve because you can search for all possible verifications of a putative answer, in parallel. This could be called "THE WHOLE BITCOIN UNDERLYING IDEA IS INHERENTLY IRRECOVERABLY STUPID" THEOREM. What I *can* easily do, is produce a problem which is inherently serial to solve, but once it is solved, the verification can be done parallel. For example, say F() is a strong encryption function. Ask: "how many times do you need to iterate F starting from X, before you reach a word whose first N bits all are 0?" This seems inherently serial and exponentially hard. But, if I solve it, I can publish the intermediate iterates, and then the facts x[k+1]=F(x[k]) and none of the x[k] begin with N zeros, can be verified for all k in parallel. This sucks since there is exponential amount of stuff to publish clogging your memory, but aside from that it works. More generally, the "PCP theorem" shows every problem in NP is, once solved, *very* quickly verifiable, if the solver publishes a (quite long, but polynomially long) proof. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)