सुपर मारियो एनपी पूरा साबित करता है

पाँच क्लासिक निनटेंडो खेलों की कम्प्यूटेशनल जटिलता के विश्लेषण से पता चला कि उनमें एनपी-पूर्ण समस्याएं हैं, जो कि तथाकथित गैर-नियतात्मक ट्यूरिंग मशीनों पर बहुपद समय में हल की जा सकती हैं। सीधे शब्दों में कहें, ये गणितीय रूप से बहुत जटिल समस्याएं हैं, जो यात्रा करने वाले सेल्समैन की समस्या या ग्राफ़ को रंगने की समस्या से तुलनीय हैं।

वैज्ञानिकों ने निम्नलिखित खेलों का विश्लेषण किया है: मारियो, गधा काँग, लीजेंड ऑफ ज़ेल्डा, मेट्रॉइड और पोकेमॉन। जैसा कि यह निकला, एनपी-पूर्णता की परिभाषा मारियो और गधा काँग श्रृंखला के सभी खेलों पर लागू होती है। अन्य श्रृंखला के कुछ खेल एनपी वर्ग के हैं, और कुछ खेल PSPACE वर्ग के हैं।

बेशक, मारियो गेम के वाणिज्यिक संस्करणों को विशेष रूप से डिज़ाइन किया गया था ताकि स्तरों को पारित किया जा सके, लेकिन इस अध्ययन के हिस्से के रूप में, वैज्ञानिकों ने बूलियन फ़ार्मुलों की व्यवहार्यता की तार्किक समस्या को कम करने के लिए स्तरों को बदल दिया और यह जांचने के लिए कि क्या फार्मूले में किसी भी चर को असाइन किया जा सकता है। असत्य और सत्य ताकि सूत्र सत्य हो जाए। इस सूत्र में चर खेल के मैदान पर विरोधी और बोनस हैं। यदि वे आपको स्तर को अंत तक पूरा करने की अनुमति देते हैं, तो सूत्र सत्य है। यदि स्तर पास करना असंभव है, तो एक विरोधाभास है।

डेवलपर के दृष्टिकोण से, एनपी-पूर्ण गेम मुश्किल हैं क्योंकि शुरू में यह जांचने का कोई आसान तरीका नहीं है कि गेम को अंत तक पूरा करना संभव है या नहीं। दूसरी ओर, इस तरह के खेल खिलाड़ियों के लिए बहुत दिलचस्प होंगे, न्यू साइंटिस्ट लिखते हैं ।