El juego de la vida de Conway: ¿Es realmente P-completado?

Question

reclamaciones de Wikipedia que el juego de la vida es P-Completa (o el problema de la decisiónLa versión de IT es; La versión de función, supongo, sería entonces FP-Completa).

Los problemas completos coloquialmente, P completos y FP, son difíciles, si no imposibles, paralelizar.Sin embargo, la mayoría de los software para evaluar el juego de la vida se paralelizan.Los algoritmos no son tan difíciles de entender.Esto parece estar en conflicto.Que esta pasando?¿Se equivoca Wikipedia, o malinterpreto algo?

Answer 1

Su malentendido es el significado de paralelizado .

En este contexto, un algoritmo se puede paralelizar si se usa polinomialmente muchos procesadores, puede calcular la respuesta (en este caso, el valor de alguna célula) en polilogarítmica .

Simulando el juego de la vida naivamente requiere tiempo proporcional a la cantidad de pasos.P-integridad del juego de la vida significa que no puede mejorar esto al tiempo polilogarítmico en el número de pasos (a menos que $ \ mathsf {p}=mathsf {nc} $ ).