3 ms·
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 t
by Cerium 3y ago
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 https://en.m.wikipedia.org/wiki/P-complete
- fooker 3y agoIt'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.