patternMinor
Conway's Game of Life: Is it really P-complete?
Viewed 0 times
reallyconwaycompletegamelife
Problem
Wikipedia claims that the Game of Life is P-complete (or the decision problem version of it is; the function version, I suppose, would then be FP-complete).
Colloquially, P-complete and FP-complete problems are difficult, if not impossible, to parallelize. However, most software for evaluating the Game of Life is parallelized. The algorithms aren't even that hard to understand. This seems to be in conflict. What is going on? Is Wikipedia wrong, or do I misunderstand something?
Colloquially, P-complete and FP-complete problems are difficult, if not impossible, to parallelize. However, most software for evaluating the Game of Life is parallelized. The algorithms aren't even that hard to understand. This seems to be in conflict. What is going on? Is Wikipedia wrong, or do I misunderstand something?
Solution
Your misunderstanding is the meaning of parallelize.
In this context, an algorithm can be parallelized if using polynomially many processors, you can compute the answer (in this case, the value of some cell) in polylogarithmic time.
Simulating the Game of Life naively takes time proportional to the number of steps. P-completeness of the Game of Life means that you cannot improve this to time polylogarithmic in the number of steps (unless $\mathsf{P}=\mathsf{NC}$).
In this context, an algorithm can be parallelized if using polynomially many processors, you can compute the answer (in this case, the value of some cell) in polylogarithmic time.
Simulating the Game of Life naively takes time proportional to the number of steps. P-completeness of the Game of Life means that you cannot improve this to time polylogarithmic in the number of steps (unless $\mathsf{P}=\mathsf{NC}$).
Context
StackExchange Computer Science Q#128414, answer score: 3
Revisions (0)
No revisions yet.