News for hackers. Stuff that matters.

A comment on NP-hard does not mean hard (2017). Parent comment

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.

[ Parent | on HN ]
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?

[ Parent | on HN ]
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...

[ Parent | on HN ]
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.
[ Parent | on HN ]
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?
[ Parent | on HN ]
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.
[ Parent | on HN ]