Jeu de la vie de Conway: est-ce vraiment p-complète?

Question

Wikipedia affirme que le jeu de la vie est complet (ou le problème de décisionLa version de celui-ci est; la version de la fonction, je suppose, serait alors FP-complète).

Les problèmes de manière familière, p-complète et FP-Terminal sont difficiles, sinon impossibles, à paralléliser.Cependant, la plupart des logiciels pour évaluer le jeu de la vie sont parallélédize.Les algorithmes ne sont même pas si difficiles à comprendre.Cela semble être en conflit.Que se passe-t-il?Wikipedia est mal ou j'ai mal compris quelque chose?

Answer 1

Votre malentendu est la signification de parallèle .

Dans ce contexte, un algorithme peut être parallélédiisé si l'utilisation de processeurs polynomésièrement nombreux, vous pouvez calculer la réponse (dans ce cas, la valeur de certaines cellules) dans polylogarithmic temps.

Simuler le jeu de la vie naïvement prend du temps proportionnel au nombre d'étapes.P-complétude du jeu de la vie signifie que vous ne pouvez pas améliorer cela pour le temps polylogarithmique dans le nombre d'étapes (sauf si $ \ mathsf {p}=mathsf {nc} $ ).