News for hackers. Stuff that matters.
Re:NP-hard does not mean hard (2017) by fooker on Thursday August 17, 2023 @01:52AM (#37157757)
Yes, linear(-ish) dependency chains so that your threads have to wait for one thread to provide a result (infinitely often).
Re:NP-hard does not mean hard (2017) by gnull on Thursday August 17, 2023 @02:57AM (#37158148)
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"?
Re:NP-hard does not mean hard (2017) by fooker on Thursday August 17, 2023 @03:06AM (#37158218)
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.
Re:NP-hard does not mean hard (2017) by gnull on Thursday August 17, 2023 @06:34PM (#37169122)
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.