एनपी जटिलता को समझना: परिभाषा और उदाहरण
एनपी का मतलब "नॉनडेटर्मिनिस्टिक पॉलिनोमियल टाइम" है। यह एक जटिलता वर्ग है जो किसी समस्या को हल करने के लिए आवश्यक समय को संदर्भित करता है। एनपी में, एल्गोरिदम का चलने का समय इनपुट के आकार में बहुपद हो सकता है, लेकिन यह गैर-नियतात्मक भी हो सकता है, जिसका अर्थ है कि चलने का समय एल्गोरिदम द्वारा चुने गए विशिष्ट समाधान के आधार पर भिन्न हो सकता है।
दूसरे शब्दों में, एनपी एक है समस्याओं का वह वर्ग जिसे गैर-नियतात्मक मशीन पर बहुपद समय में हल किया जा सकता है। एक गैर-नियतात्मक मशीन एक ऐसी मशीन है जो समानांतर में किसी समस्या के सभी संभावित समाधानों का प्रयास कर सकती है, और जो पहला काम करता है उसे स्वीकार कर सकती है। यह मशीन को नियतिवादी मशीन की तुलना में कुछ समस्याओं को बहुत तेजी से हल करने की अनुमति देता है, जो एक समय में केवल एक ही समाधान का प्रयास कर सकता है। एनपी में समस्याओं के कुछ उदाहरणों में शामिल हैं: सबसे छोटा संभव मार्ग खोजें जो प्रत्येक शहर में ठीक एक बार जाता हो)
* नैपसैक समस्या (वस्तुओं का एक सेट और उनके वजन और मूल्यों को देखते हुए, सीमित क्षमता के नैपसेक में शामिल करने के लिए वस्तुओं का सबसेट निर्धारित करें जो कुल मूल्य को अधिकतम करता है)
* बूलियन संतुष्टि समस्या (बूलियन चर और उनकी बाधाओं का एक सेट दिया गया है, यह निर्धारित करें कि क्या चर के लिए मूल्यों का एक असाइनमेंट मौजूद है जो सभी बाधाओं को संतुष्ट करता है)
एनपी जटिलता वर्ग महत्वपूर्ण है क्योंकि इसमें कई समस्याएं शामिल हैं जिन्हें बहुपद में हल करना मुश्किल है समय, लेकिन नियतिवादी मशीन द्वारा शीघ्रता से सत्यापित किया जा सकता है। इसका मतलब यह है कि भले ही एक एल्गोरिथ्म बहुपद समय में समाधान खोजने में सक्षम न हो, फिर भी यह उपयोगी हो सकता है यदि यह प्रस्तावित समाधान को शीघ्रता से सत्यापित कर सके।
मुझे यह पसंद है
मुझे यह नापसंद है
सामग्री त्रुटि की रिपोर्ट करें
शेयर करें
