[fooker]

It's not by definition, there's a bit of math behind it! :)

The intuition is that the hardest problems in P have linear dependency chains. If you could have a good parallel algorithm for a P complete problem, you could take a problem with a dependency chain and solve parts of it in parallel without waiting for the results those parts are depending on.

[gnull]

Cerium is correct, we don't know if P is efficiently parallelizable.

Is there a formal proof of what you're talking about that we can read?

[fooker]

Are you perhaps confusing P with P complete?

https://www.researchgate.net/profile/Walter-Ruzzo/publicatio...

[hgsgm]

How does that matter? P-Complete is a subset of P.

[gnull]

What am I looking for in this 300 page document? Proof by intimidation, eh?

[nine_k]

There is an easy daily example: the PBKDF function, the whole point of which is to be expensive to compute, and impossible to efficiently parallelize.