Il gioco della vita di Conway: è davvero completo?

Question

Wikipedia afferma che il gioco della vita è P-Complete (o il problema decisionalela versione è; la versione della funzione, suppongo, sarebbe quindi FP-Complete).

Coroquialmente, i problemi completi P-completi e FP-completi sono difficili, se non impossibili, di parallelizzare.Tuttavia, la maggior parte dei software per valutare il gioco della vita è parallelizzante.Gli algoritmi non sono nemmeno così difficili da capire.Questo sembra essere in conflitto.Cosa sta succedendo?Wikipedia è sbagliato, o mi fraintende qualcosa?

Answer 1

Il tuo fraintendimento è il significato di parallelize .

In questo contesto, un algoritmo può essere parallelizzato se utilizzano molti processori polinomiamente, è possibile calcolare la risposta (in questo caso, il valore di qualche cella) in polillogaritmico .

Simulazione del gioco della vita richiede ingenuamente il tempo proporzionale al numero di passaggi.La completezza del gioco della vita significa che non è possibile migliorare questo al tempo Polylogaritmico nel numero di passaggi (a meno che $ \ mathsf {p}=mathsf {nc} $ ).