Conwayの人生のゲーム：それは本当にp-completeですか？

Question

Wikipediaクレーム人生のゲームはP-Complete（または決定問題のバージョンはあります。関数のバージョン、私は、FP-Completeになります）。

ゾラボリ、P-CompleteおよびFP完全な問題は、不可能ではない場合は困難です。しかし、生活のゲームを評価するためのほとんどのソフトウェアが並列化されています。アルゴリズムは理解するのが難しいことさえありません。これは矛盾しているようです。何が起こっている？ウィキペディアが間違っているか、私は何かを誤解していますか？

Answer 1

あなたの誤解は並列化の意味です。

これに関連して、多項式的に多くのプロセッサを使用すると、 Polylog 時間の答え（この場合はいくつかのセルの値）を計算することができます。

寿命のゲームをシミュレーションする素朴には、ステップ数に比例します。人生のゲームのP-ProtersESは、ステップ数のポリロガルモトリックの時間を改善できないことを意味します（ $ \ mathsf {p}=mathsf {nc} $ ）