Conways Spiel des Lebens: Ist es wirklich p-komplett?

Question

Wikipedia behauptet , dass das Spiel des Lebens p-komplett ist (oder das EntscheidungsproblemVersion davon ist; Die Funktionsversion, die ich angenommen habe, wäre dann FP-komplett).

Umgangssprachiger, P-Complete und FP-vollständige Probleme sind schwierig, wenn nicht unmöglich, um zu parallelisieren.Die meisten Software zur Bewertung des Lebensspiels wird jedoch parallelisiert.Die Algorithmen sind nicht sogar schwer zu verstehen.Dies scheint in Konflikt zu sein.Was ist los?Ist Wikipedia falsch, oder habe ich etwas falsch verstanden?

Answer 1

Ihr Missverständnis ist die Bedeutung von parallelize .

In diesem Zusammenhang kann ein Algorithmus parallelisiert werden, wenn mehrere Prozessoren verwendet werden, können Sie die Antwort (in diesem Fall den Wert einiger Zelle) in polylogarithmischen -Zeit berechnen.

Das Simulieren des Lebensspiels nimmt naiv naiv Zeit, die proportional zur Anzahl der Schritte nimmt.P-Vollständigkeit des Spiels des Lebens bedeutet, dass Sie dies nicht in der Anzahl der Zeit nicht verbessern können>).