वर्ग NP, गैर-निर्धारित बहुपद समयको लागि उभिएको, कम्प्युटेशनल जटिलता सिद्धान्तको केन्द्रबिन्दु हो र बहुपद-समय प्रमाणिकरणहरू भएका निर्णय समस्याहरू समावेश गर्दछ। एउटा निर्णय समस्या भनेको हो वा होइन जवाफ चाहिन्छ, र यस सन्दर्भमा प्रमाणिकरणकर्ता एउटा एल्गोरिदम हो जसले दिइएको समाधानको शुद्धता जाँच गर्दछ।
समस्या समाधान गर्ने (गणना) र समाधान प्रमाणीकरण (प्रमाणीकरण) बीचको भिन्नता छुट्याउन महत्त्वपूर्ण छ। NP मा फोकस छ कि त्यहाँ एक बहुपद-समय प्रमाणिकरण छ कि समाधानको शुद्धता पुष्टि गर्न सक्छ।
वर्ग P, बहुपद समय को प्रतिनिधित्व गर्दै, निर्णय समस्याहरू समावेश गर्दछ जुन बहुपद समय भित्र एक निर्धारणात्मक ट्युरिङ मेसिन द्वारा समाधान गर्न सकिन्छ। यसरी, P मा प्रत्येक समस्याको लागि, त्यहाँ समाधान खोज्नको लागि बहुपद-समय एल्गोरिथ्म मात्र होइन, तर समाधान प्रमाणित गर्न बहुपद-समय एल्गोरिदम पनि छ।
देखिने विरोधाभास यो अवलोकनमा निहित छ कि P मा प्रत्येक समस्या, स्वाभाविक रूपमा बहुपद-समय समाधान गर्ने एल्गोरिदम भएको, बहुपद-समय प्रमाणिकरणकर्ता पनि हुन्छ। यद्यपि, यसले NP को परिभाषाको विरोध गर्दैन। NP को परिभाषित विशेषता एक बहुपद-समय प्रमाणिकरणको अस्तित्व हो, समाधान खोज्न कति समय लाग्न सक्छ। यसको मतलब P मा सबै समस्याहरू NP मा पनि छन्, किनकि तिनीहरूको समाधान बहुपदीय समयमा प्रमाणित गर्न सकिन्छ।
उदाहरणका लागि, प्राइम नम्बर परीक्षणको समस्यालाई विचार गर्नुहोस्। यो समस्यालाई दुई तरिकामा बनाउन सकिन्छ: प्राइम नम्बरहरू उत्पन्न गर्ने र दिइएको नम्बर प्राइम हो कि छैन भनी प्रमाणित गर्ने। Eratosthenes को सिभ एक निश्चित सीमा सम्म सबै अविभाज्य संख्याहरू उत्पन्न गर्न को लागी एक एल्गोरिथ्म हो र यति कुशलतापूर्वक गर्छ, तर यसको समय जटिलता कम्प्यूटेशनल जटिलता सिद्धान्तमा प्रयोग गरिएको कडा अर्थमा बहुपद होइन; यसलाई प्राय: O(n log log n) को रूपमा चिनिन्छ, जुन P को परिभाषा अनुसार रैखिक भन्दा राम्रो तर कडा बहुपद होइन। अर्कोतर्फ, दिइएको संख्या प्राइम (प्राइम नम्बर परीक्षण) हो कि होइन भनेर प्रमाणित गर्ने समस्या हो। एक फरक कार्य। कुशल एल्गोरिदमहरू जस्तै AKS प्राथमिकता परीक्षणले बहुपदीय समयमा प्राइम प्रमाणिकरणको लागि अनुमति दिन्छ। तसर्थ, प्राइम नम्बर परीक्षण समस्या, प्रमाणीकरणको सन्दर्भमा, वर्ग P, साथै NP मा पर्छ, किनभने समाधान (अङ्क प्राइम हो कि होइन) बहुपदीय समयमा प्रमाणित गर्न सकिन्छ। यसले देखाउँछ कि प्राइम नम्बर जेनरेशन र प्राइम नम्बर परीक्षण सम्बन्धित छन्, तिनीहरू कम्प्यूटेशनल जटिलताको सन्दर्भमा फरक विचारहरू समावेश गर्दछ।
अन्तमा, बहुपद-समय प्रमाणिकरणहरू भएको NP को परिभाषा P को प्रकृतिसँग मिल्छ। भिन्नता प्रमाणिकरण चरणमा होइन तर समाधानहरू खोज्ने प्रक्रियामा छ: P समस्याहरू बहुपदीय समयमा समाधान गर्न सकिने र प्रमाणिकरणयोग्य हुन्छन्, जबकि NP समस्याहरू बहुपद समयमा प्रमाणित हुन्छन्, तर बहुपद समयमा समाधान गर्न सकिन्छ कि भनेर सधैं थाहा हुँदैन।
अन्य भर्खरका प्रश्न र उत्तरहरू सम्बन्धमा जटिलता:
- के PSPACE वर्ग EXPSPACE वर्गको बराबर छैन?
- के P जटिलता वर्ग PSPACE वर्गको उपसमूह हो?
- के हामी एक निश्चित TM मा कुनै पनि NP पूर्ण समस्याको लागि एक कुशल बहुपद समाधान खोजेर Np र P वर्ग समान छन् भनेर प्रमाणित गर्न सक्छौं?
- के NP वर्ग EXPTIME कक्षा बराबर हुन सक्छ?
- के PSPACE मा समस्याहरू छन् जसको लागि कुनै ज्ञात NP एल्गोरिथ्म छैन?
- के एक SAT समस्या NP पूर्ण समस्या हुन सक्छ?
- के NP जटिलता वर्गमा समस्या हुन सक्छ यदि त्यहाँ एक गैर-निर्धारित ट्युरिङ मेसिन छ जसले यसलाई बहुपद समयमा समाधान गर्नेछ।
- NP बहुपदीय समय प्रमाणिकरण भएका भाषाहरूको वर्ग हो
- के P र NP वास्तवमा एउटै जटिलता वर्ग हो?
- के प्रत्येक सन्दर्भ मुक्त भाषा P जटिलता वर्गमा छ?
जटिलतामा थप प्रश्न र उत्तरहरू हेर्नुहोस्