Computer Science Asked by fluffysheap on October 21, 2021
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?
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}$).
Answered by Yuval Filmus on October 21, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP