नियतात्मक बनाम नॉनडेर्मिनिस्टिक अभिकलन
कक्षा को समझने के लिए P तथा NP, पहले हमें कम्प्यूटेशनल मॉडल को जानना चाहिए। इसलिए, इस अध्याय में हम दो महत्वपूर्ण कम्प्यूटेशनल मॉडल पर चर्चा करेंगे।
नियतात्मक संगणना और कक्षा पी
नियतात्मक ट्यूरिंग मशीन
इन मॉडलों में से एक नियतात्मक एक-टेप ट्यूरिंग मशीन है। इस मशीन में एक परिमित राज्य नियंत्रण, एक रीड-राइट हेड और अनंत अनुक्रम के साथ एक दो-तरफा टेप होता है।
निम्नलिखित एक नियतात्मक एक-टेप ट्यूरिंग मशीन का योजनाबद्ध आरेख है।
नियतात्मक ट्यूरिंग मशीन के लिए एक कार्यक्रम निम्नलिखित जानकारी निर्दिष्ट करता है -
- टेप प्रतीकों का एक परिमित सेट (इनपुट प्रतीक और एक खाली प्रतीक)
- राज्यों का एक निर्धारित सेट
- एक संक्रमण समारोह
एल्गोरिथमिक विश्लेषण में, यदि कोई समस्या नियतात्मक एक टेप ट्यूरिंग मशीन द्वारा बहुपद समय में हल करने योग्य है, तो समस्या P वर्ग की है।
Nondeterministic कम्प्यूटेशन और क्लास एनपी
नॉनडेर्मिनिस्टिक ट्यूरिंग मशीन
कम्प्यूटेशनल समस्या को हल करने के लिए, एक अन्य मॉडल गैर-नियतात्मक ट्यूरिंग मशीन (NDTM) है। एनडीटीएम की संरचना डीटीएम के समान है, हालांकि यहां हमारे पास एक अतिरिक्त मॉड्यूल है जो अनुमान लगाने वाले मॉड्यूल के रूप में जाना जाता है, जो एक राइट-ओनली हेड के साथ जुड़ा हुआ है।
निम्नलिखित योजनाबद्ध आरेख है।
यदि समस्या एक गैर-नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद समय में हल है, तो समस्या एनपी वर्ग की है।