لعبة Conway's Life: هل هي حقا p-complete؟

Question

مطالبات ويكيبيديا أن لعبة الحياة هي P-Complete (أو مشكلة القرارنسخة منه هو؛ إصدار الوظيفة، أفترض، سوف يكون إكمال FP).

colloquially، مشاكل كاملة من P-Complete و FP صعبة، إن لم تكن مستحيلة، بالتوازي.ومع ذلك، فإن معظم البرامج لتقييم لعبة الحياة متوازية.الخوارزميات ليست صعوبة في فهمها.يبدو أن هذا في صراع.ما الذي يجري؟هل ويكيبيديا خاطئة، أو هل أسيء فهم شيء ما؟

Answer 1

سوء فهمك هو معنى متوازي .

في هذا السياق، يمكن توزز الخوارزمية إذا كنت تستخدم العديد من المعالجات متعددة الحدود، فيمكنك حساب الإجابة (في هذه الحالة، قيمة بعض الخلية) في polylogaritmic الوقت.

محاكاة لعبة الحياة تستغرق الوقت بما يتناسب مع عدد الخطوات.P-اكتمال لعبة الحياة يعني أنه لا يمكنك تحسين ذلك إلى وقت البوليات في الوقت في عدد الخطوات (ما لم يكن $ \ mathsf {p}=mathsf {nc} $ ).