डीएए - पी एंड एनपी क्लास
कंप्यूटर विज्ञान में, कई समस्याएं हल की जाती हैं जहां उद्देश्य कुछ मूल्यों को अधिकतम या कम करना है, जबकि अन्य समस्याओं में हम यह खोजने की कोशिश करते हैं कि कोई समाधान है या नहीं। इसलिए, समस्याओं को निम्नानुसार वर्गीकृत किया जा सकता है -
अनुकूलन समस्या
अनुकूलन समस्याएं वे हैं जिनके लिए उद्देश्य कुछ मूल्यों को अधिकतम या कम करना है। उदाहरण के लिए,
दिए गए ग्राफ़ को रंग देने के लिए आवश्यक न्यूनतम रंगों की खोज करना।
एक ग्राफ में दो कोने के बीच सबसे छोटा रास्ता खोजना।
निर्णय की समस्या
ऐसी कई समस्याएं हैं जिनके लिए उत्तर हां या नहीं है। इन प्रकार की समस्याओं को जाना जाता है decision problems। उदाहरण के लिए,
क्या किसी दिए गए ग्राफ को केवल 4 रंगों में रंगा जा सकता है।
ग्राफ में हैमिल्टनियन चक्र खोजना कोई निर्णय समस्या नहीं है, जबकि ग्राफ की जाँच करना हैमिल्टनियन है या नहीं यह निर्णय समस्या है।
भाषा क्या है?
हर निर्णय समस्या के केवल दो उत्तर हो सकते हैं, हाँ या नहीं। इसलिए, एक निर्णय समस्या एक भाषा से संबंधित हो सकती है यदि यह एक विशिष्ट इनपुट के लिए उत्तर 'हां' प्रदान करती है। एक भाषा आदानों की समग्रता है जिसके लिए उत्तर हां है। पिछले अध्यायों में चर्चा किए गए अधिकांश एल्गोरिदम हैंpolynomial time algorithms।
इनपुट आकार के लिए n, अगर किसी एल्गोरिथम का सबसे खराब समय जटिलता है O(nk), कहाँ पे k एक स्थिर है, एल्गोरिथ्म एक बहुपद समय एल्गोरिथ्म है।
मैट्रिक्स चेन मल्टीप्लिमेंटेशन, सिंगल सोर्स शॉर्टेस्ट पाथ, ऑल पेयर शॉर्टेस्ट पाथ, मिनिमम स्पैनिंग ट्री आदि जैसे एल्गोरिदम बहुपद काल में चलते हैं। हालांकि कई समस्याएं हैं, जैसे यात्रा करने वाले विक्रेता, इष्टतम ग्राफ रंग, हैमिल्टनियन चक्र, एक ग्राफ में सबसे लंबा रास्ता खोजना, और एक बूलियन फार्मूला को संतुष्ट करना, जिसके लिए कोई बहुपद समय एल्गोरिदम ज्ञात नहीं है। ये समस्याएं समस्याओं के एक दिलचस्प वर्ग से संबंधित हैं, जिन्हें कहा जाता हैNP-Complete समस्याएं, जिनकी स्थिति अज्ञात है।
इस संदर्भ में, हम समस्याओं को निम्नानुसार वर्गीकृत कर सकते हैं -
पी वर्ग
कक्षा P में उन समस्याओं का समावेश होता है जो बहुपद समय में हल करने योग्य होती हैं, अर्थात इन समस्याओं को समय रहते हल किया जा सकता है O(nk) सबसे खराब स्थिति में, कहाँ k स्थिर है।
इन समस्याओं को कहा जाता है tractable, जबकि दूसरों को बुलाया जाता है intractable or superpolynomial।
औपचारिक रूप से, एक एल्गोरिथ्म बहुपद समय एल्गोरिथ्म है, यदि एक बहुपद मौजूद है p(n) एल्गोरिथ्म आकार के किसी भी उदाहरण को हल कर सकता है n एक समय में O(p(n))।
समस्या की आवश्यकता है Ω(n50) हल करने के लिए समय अनिवार्य रूप से बड़े के लिए अचूक है n। अधिकांश ज्ञात बहुपद समय एल्गोरिथ्म समय में चलते हैंO(nk) के काफी कम मूल्य के लिए k।
बहुपद-काल के एल्गोरिदम के वर्ग पर विचार करने में लाभ यह है कि सभी उचित हैं deterministic single processor model of computation एक बहुपत्नी धीमे-धीमे एक दूसरे के साथ अनुकरण किया जा सकता है
एनपी क्लास
क्लास एनपी में उन समस्याओं का समावेश होता है जो बहुपद समय में सत्य हैं। एनपी निर्णय की समस्याओं का वर्ग है, जिसके लिए थोड़े अतिरिक्त जानकारी की सहायता से, एक अनुमानित उत्तर की शुद्धता की जांच करना आसान है। इसलिए, हम समाधान खोजने का तरीका नहीं पूछ रहे हैं, लेकिन केवल यह सत्यापित करने के लिए कि एक कथित समाधान वास्तव में सही है।
इस वर्ग की हर समस्या का विस्तृत समय पर हल किया जा सकता है।
पी बनाम एनपी
प्रत्येक निर्णय समस्या जो एक नियतात्मक बहुपद समय एल्गोरिथ्म द्वारा हल करने योग्य है, एक बहुपद समय गैर-नियतात्मक एल्गोरिथ्म द्वारा हल भी है।
पी में सभी समस्याओं को बहुपद समय एल्गोरिदम के साथ हल किया जा सकता है, जबकि एनपी - पी में सभी समस्याएं अचूक हैं।
यह ज्ञात नहीं है कि क्या P = NP। हालांकि, एनपी में कई समस्याओं को संपत्ति के साथ जाना जाता है यदि वे पी से संबंधित हैं, तो यह साबित किया जा सकता है कि पी = एनपी।
अगर P ≠ NPएनपी में समस्याएं हैं जो न तो पी में हैं और न ही एनपी-पूर्ण में हैं।
समस्या वर्ग की है Pअगर समस्या का हल खोजना आसान है। समस्या का हैNP, अगर यह एक समाधान की जांच करना आसान है जो खोजने के लिए बहुत थकाऊ हो सकता है।