I am looking for a proof-of-work scheme which cannot be effectively parallelized.
For example, in hashcash (and by extension bitcoin) you have some collision-resistant hash function $f()$, a target $T$ and some constant $C$. You obtain the proof of work by running $P=f(C, N)$ for some nonce $N$ which gets incremented with each iteration, untill $P\lt T$ (intuitive definition). The computee then publishes $C, N$ and the verifier verifies the condition by running the hash function once.
This can be easily parallelized by using multiple processors and assigning a portion of $N$ to each one.
I know scrypt aims to be memory-intensive and thus expensive and that bcrypt does something similar.
My approach so far is to use a secondary proof by obtaining $P$ as described above and then running $C' \gets P$ and $P'=f(C',N')$ untill $P'\lt T$ as above. This forces a parallel environment to do the same job as the first scheme, provided the adversary can only afford $max(N)$ processors. It also prohibits the use of single-processor systems (and it's kind of a dumb solution anyway).
I tried to look into literature but unfortunately I'm not mature enough for it. I also understand my question is borderline reference-request but I think I could argue it is acceptable. I leave judgement to you.
To conclude: Is there a proof-of-work scheme based on some hard-to-parallelize (P-complete) problem? Intuition tells me this is a problem based on work (repetition) so it is inherently parallelizable.