[s1dev]

Is there some good intuition why P-complete problems are difficult to parallelize? This is the first I've heard of it (but then again, I'm usually interested in more obscure complexity classes)

[Cerium]

This is the first I have heard of it as well (and I have properly studied NP complete in graph theory, so I don't know why this missed my attention). It seems that P-complete are difficult to parallelize by definition as they are the set of tractable problems (as opposed to NP) which don't parallelize well.

"The class P, typically taken to consist of all the "tractable" problems for a sequential computer, contains the class NC, which consists of those problems which can be efficiently solved on a parallel computer. This is because parallel computers can be simulated on a sequential machine. It is not known whether NC = P. In other words, it is not known whether there are any tractable problems that are inherently sequential. " From: https://en.m.wikipedia.org/wiki/P-complete

[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.

[fooker]

Yes, linear(-ish) dependency chains so that your threads have to wait for one thread to provide a result (infinitely often).

[gnull]

Are you stretching "this specific strategy for parallelizing P that I came up with won't work" to "there's no way to parallelize P"?

[fooker]

It’s more like : you win a Turing award by finding a strategy to parallelize this problem as you’ll be able to use that approach to parallelize all problems in P, proving NC = P.

[gnull]

This applies both ways. You'll win a Turing award if you prove NC ≠ P, which is kind of what you said — at least, that the best way I see of reading your first and a few following messages.