News for hackers. Stuff that matters.
Re:NP-hard does not mean hard (2017) by Cerium on Thursday August 17, 2023 @01:53AM (#37157759)
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

Re:NP-hard does not mean hard (2017) by fooker on Thursday August 17, 2023 @01:58AM (#37157787)
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.

Re:NP-hard does not mean hard (2017) by gnull on Thursday August 17, 2023 @02:53AM (#37158118)
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?

Re:NP-hard does not mean hard (2017) by fooker on Thursday August 17, 2023 @02:55AM (#37158140)
Are you perhaps confusing P with P complete?

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

Re:NP-hard does not mean hard (2017) by hgsgm on Thursday August 17, 2023 @11:11AM (#37162913)
How does that matter? P-Complete is a subset of P.
Re:NP-hard does not mean hard (2017) by gnull on Thursday August 17, 2023 @06:35PM (#37169139)
What am I looking for in this 300 page document? Proof by intimidation, eh?
Re:NP-hard does not mean hard (2017) by nine_k on Thursday August 17, 2023 @03:27AM (#37158351)
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.