5
$\begingroup$

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?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
3
$\begingroup$

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}$).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.