Conway的生活游戏：它真的是p-完成吗？

Question

维基百科索赔那些生命游戏是p-完成（或决策问题版本是;函数版本，我想，然后是fp-complete）。

巧妙地，如果不是不可能的话，难以平行的p-cleant和fp-complete问题。但是，大多数用于评估生命游戏的软件都是平行化的。算法甚至不难以理解。这似乎在冲突中。到底是怎么回事？是wikipedia错了，或者我误解了什么？

Answer 1

您的误解是并行化的含义。

在此上下文中，如果使用多项式的处理器，可以将算法并行化，您可以计算答案（在这种情况下，某些单元格值）在 polylogarithmic 时间中。

模拟生命游戏天鹅绒花费时间与步骤数量成比例。生命游戏的p完整性意味着您不能在步骤数量（除非 $ \ mathsf {p}=mathsf {nc} $ ）。