3 ms·
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
by fooker 3y ago
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 3y agoCerium 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 3y agoAre you perhaps confusing P with P complete? https://www.researchgate.net/profile/Walter-Ruzzo/publication/222089821_Limits_to_Parallel_Computation_P-Completeness_Theory/links/54fc88560cf20700c5e96c56/Limits-to-Parallel-Computation-P-Completeness-Theory.pdf https://www.researchgate.net/profile/Walter-Ruzzo/publicatio...
- nine_k 3y agoThere is an easy daily example: the PBKDF function, the whole point of which is to be expensive to compute, and impossible to efficiently parallelize.