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 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 ]