एनपी (जटिलता): Difference between revisions

Revision as of 11:30, 25 May 2023

ट्यूरिंग मशीन – Computation model defining an abstract machine

Unsolved problem in अभिकलित्र विज्ञान:

${\mathsf {P\ {\overset {?}{=}}\ NP}}$

(more unsolved problems in अभिकलित्र विज्ञान)

पी (जटिलता), एनपी, एनपी-पूर्ण, और एनपी कठिन समुच्चय समस्याओं के लिए यूलर आरेख। इस धारणा के अनुसार कि पी ≠ एनपी, एनपी के अंदर किन्तु पी और एनपी दोनों के बाहर समस्याओं का अस्तित्व-पूर्ण लेडनर का प्रमेय था।^[1]

कम्प्यूटेशनल जटिलता सिद्धांत में, एनपी (गैर-नियतात्मक बहुपद समय) जटिलता वर्ग है जिसका उपयोग निर्णय समस्याओं को वर्गीकृत करने के लिए किया जाता है। एनपी निर्णय समस्याओं का समुच्चय (गणित) है जिसके लिए कम्प्यूटेशनल जटिलता सिद्धांत या समस्या उदाहरण, जहां उत्तर "हां" है, नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद समय में गणितीय प्रमाण सत्यापन योग्य है, या वैकल्पिक रूप से समस्याओं का समुच्चय जिसे हल किया जा सकता है गैर नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद समय।^[2]^{[Note 1]}

एनपी की समतुल्य परिभाषा गैर-नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद समय में सत्यापन योग्य निर्णय समस्याओं का समूह है। यह परिभाषा संक्षिप्त नाम एनपी का आधार है; "गैर नियतात्मक एल्गोरिथम , बहुपद समय"। ये दो परिभाषाएँ समतुल्य हैं क्योंकि ट्यूरिंग मशीन पर आधारित एल्गोरिथ्म में दो चरण होते हैं, जिनमें से पहले में समाधान के बारे में अनुमान होता है, जो गैर-नियतात्मक तरीके से उत्पन्न होता है, जबकि दूसरे चरण में नियतात्मक एल्गोरिथ्म होता है जो यह सत्यापित करता है कि क्या अनुमान समस्या का समाधान है।^[3]

यह देखना आसान है कि जटिलता वर्ग पी (जटिलता) (सभी समस्याओं को हल करने योग्य, निश्चित रूप से, बहुपद समय में) एनपी में समाहित है (समस्याएं जहां बहुपद समय में समाधान सत्यापित किए जा सकते हैं), क्योंकि यदि कोई समस्या बहुपद समय में हल करने योग्य है, फिर समस्या को हल करके बहुपद समय में समाधान भी सत्यापित किया जा सकता है। किन्तु एनपी में और भी कई समस्याएं हैं,^{[Note 2]} जिनमें से सबसे कठिन को एनपी-पूर्ण समस्याएं कहा जाता है। बहुपद समय में ऐसी समस्या को हल करने वाला एल्गोरिदम बहुपद समय में किसी अन्य एनपी समस्या को हल करने में भी सक्षम है। सबसे महत्वपूर्ण पी बनाम एनपी समस्या | पी बनाम एनपी ("पी = एनपी?") समस्या, पूछती है कि क्या एनपी-पूर्ण, और परिणाम द्वारा, सभी एनपी समस्याओं को हल करने के लिए बहुपद-समय एल्गोरिदम उपस्थित हैं। यह व्यापक रूप से माना जाता है कि ऐसा नहीं है।^[4]

जटिलता वर्ग एनपी जटिलता वर्ग सह-एनपी से संबंधित है, जिसके लिए बहुपद समय में उत्तर संख्या को सत्यापित नहीं किया जा सकता है। की भी होगी या नहीं NP = co-NP जटिलता सिद्धांत में और उत्कृष्ट प्रश्न है।^[5]

औपचारिक परिभाषा

जटिलता वर्ग एनपी को एनटीआईएमई के संदर्भ में निम्नानुसार परिभाषित किया जा सकता है:

{\mathsf {NP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(n^{k}),

कहाँ ${\mathsf {NTIME}}(n^{k})$ निर्णय समस्याओं का समूह है जिसे गैर-नियतात्मक ट्यूरिंग मशीन द्वारा हल किया जा सकता है $O(n^{k})$ समय।

वैकल्पिक रूप से, एनपी को नियतात्मक ट्यूरिंग मशीनों का उपयोग सत्यापनकर्ता के रूप में परिभाषित किया जा सकता है। औपचारिक भाषा एल एनपी में है यदि और केवल यदि बहुपद पी और क्यू उपस्थित हैं, और निर्धारिती ट्यूरिंग मशीन एम, जैसे कि

सभी x और y के लिए, मशीन M इनपुट पर समय p(|x|) में चलती है $(x,y)$ .
L में सभी x के लिए, लंबाई q(|x|) की स्ट्रिंग y उपस्थित है जैसे कि $M(x,y)=1$ .
सभी x के लिए जो L में नहीं है और सभी स्ट्रिंग्स y की लंबाई q(|x|), $M(x,y)=0$ .

पृष्ठभूमि

कई कंप्यूटर विज्ञान की समस्याएं एनपी में समाहित हैं, जैसे कई खोज समस्या और अनुकूलन समस्याओं के निर्णय संस्करण।

सत्यापनकर्ता-आधारित परिभाषा

एनपी की सत्यापनकर्ता-आधारित परिभाषा को समझाने के लिए, उपसमुच्चय योग समस्या पर विचार करें: मान लें कि हमें कुछ पूर्णांक दिए गए हैं, {−7, −3, −2, 5, 8}, और हम जानना चाहते हैं कि इनमें से कुछ पूर्णांकों का योग शून्य है या नहीं। यहाँ उत्तर हाँ है, चूँकि पूर्णांक {−3, −2, 5} योग के अनुरूप हैं (−3) + (−2) + 5 = 0.

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

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

उपरोक्त उदाहरण को किसी भी निर्णय समस्या के लिए सामान्यीकृत किया जा सकता है। समस्या के किसी भी उदाहरण I को देखते हुए $\Pi$ और गवाह W, यदि कोई सत्यापनकर्ता V उपस्थित है, जिससे आदेशित जोड़ी (I, W) को इनपुट के रूप में दिया जाए, तो V बहुपद समय में हाँ लौटाता है यदि गवाह यह सिद्ध करता है कि उत्तर बहुपद समय में हाँ या नहीं है, तो फिर $\Pi$ एनपी में है।

इस समस्या का नो-उत्तर संस्करण इस प्रकार कहा गया है: पूर्णांकों का परिमित समुच्चय दिया गया है, क्या प्रत्येक गैर-खाली उपसमुच्चय में गैर-शून्य योग है? . एनपी की सत्यापनकर्ता-आधारित परिभाषा को बिना किसी उत्तर के लिए कुशल सत्यापनकर्ता की आवश्यकता नहीं होती है। बिना उत्तर वाले सत्यापनकर्ताओं के साथ समस्याओं की श्रेणी को सह-एनपी कहा जाता है। वास्तव में, यह खुला प्रश्न है कि क्या एनपी में सभी समस्याओं के पास बिना किसी उत्तर के सत्यापनकर्ता भी हैं और इस प्रकार सह-एनपी में हैं।

कुछ साहित्य में सत्यापनकर्ता को प्रमाणक कहा जाता है, और साक्षी को प्रमाण पत्र (जटिलता) कहा जाता है।^[2]

मशीन-परिभाषा

सत्यापनकर्ता-आधारित परिभाषा के समतुल्य निम्नलिखित लक्षण वर्णन है: एनपी गैर-नियतात्मक ट्यूरिंग मशीन द्वारा हल की जाने वाली निर्णय समस्याओं का वर्ग है जो बहुपद समय में चलता है। अर्थात निर्णय समस्या $\Pi$ जब भी एनपी में है $\Pi$ कुछ बहुपद-समय गैर-नियतात्मक ट्यूरिंग मशीन द्वारा मान्यता प्राप्त है $M$ अस्तित्वगत स्वीकृति शर्त के साथ, जिसका अर्थ है $w\in \Pi$ यदि यदि और केवल यदि कुछ गणना पथ $M(w)$ स्वीकार्य स्थिति की ओर ले जाता है। यह परिभाषा सत्यापनकर्ता-आधारित परिभाषा के समतुल्य है क्योंकि गैर-नियतात्मक ट्यूरिंग मशीन बहुपद समय में एनपी समस्या को गैर-निर्धारिती रूप से प्रमाण पत्र का चयन करके और प्रमाण पत्र पर सत्यापनकर्ता चलाकर हल कर सकती है। इसी तरह, यदि ऐसी कोई मशीन उपस्थित है, तो स्वाभाविक रूप से बहुपद समय सत्यापनकर्ता का निर्माण किया जा सकता है।

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

गुण

एनपी संघ ( सिद्धांत) , चौराहा , कॉन्टेनेशन, क्लेन स्टार और फॉर्मल लैंग्वेज या ऑपरेशंस ऑन लैंग्वेजेज के अनुसार बंद है। यह ज्ञात नहीं है कि क्या एनपी पूरक ( सिद्धांत) के अनुसार बंद है (यह प्रश्न तथाकथित एनपी बनाम सह-एनपी प्रश्न है)।

क्यों कुछ एनपी समस्याओं को हल करना कठिन है

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

इस संदर्भ में महत्वपूर्ण धारणा एनपी-पूर्ण निर्णय समस्याओं का समुच्चय है, जो एनपी का उप समुच्चय है और इसे अनौपचारिक रूप से एनपी में सबसे कठिन समस्याओं के रूप में वर्णित किया जा सकता है। यदि उनमें से "एक" के लिए बहुपद-समय एल्गोरिदम है, तो एनपी में "सभी" समस्याओं के लिए बहुपद-समय एल्गोरिदम है। इस वजह से, और क्योंकि समर्पित शोध किसी भी एनपी-पूर्ण समस्या के लिए बहुपद एल्गोरिदम खोजने में विफल रहा है, बार समस्या एनपी-पूर्ण सिद्ध हो जाने के बाद, यह व्यापक रूप से संकेत के रूप में माना जाता है कि इस समस्या के लिए बहुपद एल्गोरिदम की संभावना नहीं है अस्तित्व के लिए।

चूंकि , व्यावहारिक उपयोगों में, इष्टतम समाधान की तलाश में कम्प्यूटेशनल संसाधनों को खर्च करने के अतिरिक्त , बहुपद समय में अच्छा पर्याप्त (किन्तु संभावित उप-इष्टतम) समाधान अधिकांशतः पाया जा सकता है। साथ ही, कुछ समस्याओं के वास्तविक जीवन के अनुप्रयोग उनके सैद्धांतिक समकक्षों की तुलना में आसान होते हैं।

परिभाषाओं की समानता

बहुपद समय में गैर-नियतात्मक ट्यूरिंग मशीन (टीएम) द्वारा हल की जाने वाली समस्याओं की श्रेणी के रूप में एनपी की दो परिभाषाएं और बहुपद समय में नियतात्मक ट्यूरिंग मशीन द्वारा सत्यापन योग्य समस्याओं का वर्ग समतुल्य है। कई पाठ्यपुस्तकों द्वारा प्रमाण का वर्णन किया गया है, उदाहरण के लिए, सिप्सर्स इंट्रोडक्शन टू द थ्योरी ऑफ़ कम्प्यूटेशन, सेक्शन 7.3।

इसे दिखाने के लिए, पहले, मान लीजिए कि हमारे पास नियतात्मक सत्यापनकर्ता है। गैर-नियतात्मक मशीन सभी संभावित प्रूफ स्ट्रिंग्स पर सत्यापनकर्ता को केवल गैर-नियतात्मक रूप से चला सकती है (इसके लिए केवल बहुपद रूप से कई चरणों की आवश्यकता होती है क्योंकि यह प्रत्येक चरण में प्रूफ स्ट्रिंग में अगला वर्ण चुन सकती है, और प्रूफ स्ट्रिंग की लंबाई बहुपद रूप से बंधी होनी चाहिए ). कोई प्रमाण मान्य होगा तो कोई मार्ग मानेगा; यदि कोई प्रमाण मान्य नहीं है, तो स्ट्रिंग भाषा में नहीं है और वह अस्वीकार कर देगा।

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

अन्य वर्गों से संबंध

जटिलता वर्गों के बीच संबंध का प्रतिनिधित्व

पी (जटिलता), एनपी (जटिलता), सह-एनपी, बीपीपी (जटिलता), पी/पॉली, पीएच (जटिलता), और पीएसपीएसीई सहित जटिलता वर्गों का समावेश

एनपी में पी (जटिलता) में सभी समस्याएं सम्मिलित हैं, क्योंकि कोई भी प्रमाण को अनदेखा करके और इसे हल करके समस्या के किसी भी उदाहरण को सत्यापित कर सकता है। एनपी पीएसपीएसीई में निहित है - यह दिखाने के लिए, यह पीएसपीएसीई मशीन बनाने के लिए पर्याप्त है जो सभी प्रमाण तारों पर लूप करता है और प्रत्येक को बहुपद-समय सत्यापनकर्ता को खिलाता है। चूंकि बहुपद-समय मशीन बहुपद रूप से केवल कई बिट्स पढ़ सकती है, यह बहुपद स्थान से अधिक का उपयोग नहीं कर सकती है, न ही यह बहुपद स्थान से अधिक पर कब्जा करने वाली प्रमाण स्ट्रिंग पढ़ सकती है (इसलिए हमें इससे अधिक प्रमाण पर विचार करने की ज़रूरत नहीं है)। एनपी एक्स्प्तिमे में भी समाहित है, क्योंकि ही एल्गोरिथ्म घातीय समय में संचालित होता है।

सह-एनपी में वे समस्याएं सम्मिलित हैं जिनके पास बिना किसी उदाहरण के सरल प्रमाण है, जिसे कभी-कभी प्रति उदाहरण कहा जाता है। उदाहरण के लिए, प्रारंभिक परीक्षण सह-एनपी में सामान्य रूप से निहित है, क्योंकि कोई केवल गैर-कारक कारक की आपूर्ति करके पूर्णांक की प्राथमिकता को अस्वीकार कर सकता है। एनपी और सह-एनपी मिलकर बहुपद पदानुक्रम में पहला स्तर बनाते हैं, केवल पी से अधिक।

एनपी को केवल नियतात्मक मशीनों का उपयोग करके परिभाषित किया गया है। यदि हम सत्यापनकर्ता को संभाव्य होने की अनुमति देते हैं (चूंकि , यह बीपीपी मशीन नहीं है^[6]), हम आर्थर-मर्लिन प्रोटोकॉल का उपयोग करके कक्षा एमए को हल करने योग्य पाते हैं, जिसमें आर्थर से मर्लिन तक कोई संचार नहीं है।

बीपीपी (जटिलता) और एनपी के बीच संबंध अज्ञात है: यह ज्ञात नहीं है कि बीपीपी एनपी का उप समुच्चय है, एनपी बीपीपी का उप समुच्चय है या नहीं। यदि एनपी बीपीपी में समाहित है, जिसे असंभाव्य माना जाता है क्योंकि यह एनपी-पूर्ण समस्याओं के लिए व्यावहारिक समाधान प्रदान करेगा, तो एनपी = आरपी और पीएच (जटिलता) ⊆ बीपीपी।^[7]

एनपी निर्णय समस्याओं का वर्ग है; फ़ंक्शन समस्याओं का अनुरूप वर्ग एफएनपी (जटिलता) है।

केवल ज्ञात सख्त समावेशन समय पदानुक्रम प्रमेय और अंतरिक्ष पदानुक्रम प्रमेय से आते हैं, और क्रमशः वे हैं ${\mathsf {NP\subsetneq NEXPTIME}}$ और ${\mathsf {NP\subsetneq EXPSPACE}}$ .

अन्य लक्षण

वर्णनात्मक जटिलता सिद्धांत के संदर्भ में, एनपी अस्तित्वगत दूसरे क्रम के तर्क (फागिन के प्रमेय) द्वारा परिभाषित भाषाओं के समुच्चय से स्पष्ट रूप से मेल खाता है।

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

जटिलता सिद्धांत का प्रमुख परिणाम यह है कि एनपी को संभावित रूप से जांच योग्य प्रमाण द्वारा हल करने योग्य समस्याओं के रूप में वर्णित किया जा सकता है जहां सत्यापनकर्ता ओ (लॉग एन) यादृच्छिक बिट्स का उपयोग करता है और प्रमाण स्ट्रिंग (वर्ग 'पीसीपी' वर्ग) के केवल बिट्स की निरंतर संख्या की जांच करता है। लॉग एन, 1))। अधिक अनौपचारिक रूप से, इसका कारण यह है कि ऊपर वर्णित एनपी सत्यापनकर्ता को के साथ प्रतिस्थापित किया जा सकता है जो प्रूफ स्ट्रिंग में कुछ स्थानों पर स्पॉट-चेक करता है, और सीमित संख्या में सिक्का फ़्लिप का उपयोग करके उच्च संभावना के साथ सही उत्तर निर्धारित कर सकता है। यह सन्निकटन एल्गोरिदम की कठोरता के बारे में कई परिणाम सिद्ध करने की अनुमति देता है।

उदाहरण

पी

पी (जटिलता) में सभी समस्याएं, निरूपित ${\mathsf {P\subseteq NP}}$ . पी में किसी समस्या के लिए प्रमाण पत्र दिया गया है, हम प्रमाण पत्र को अनदेखा कर सकते हैं और बहुपद समय में समस्या को हल कर सकते हैं।

पूर्णांक गुणनखंड

पूर्णांक गुणनखंडन समस्या का निर्णय समस्या संस्करण: दिए गए पूर्णांक n और k, क्या 1 < f < k और f विभाजन n के साथ कोई कारक f है?^[8]

एनपी-पूर्ण समस्याएं

प्रत्येक एनपी-पूर्णता | एनपी-पूर्ण समस्या एनपी में है।

बूलियन संतुष्टि

बूलियन संतुष्टि समस्या (एसएटी), जहां हम जानना चाहते हैं कि बूलियन चर के साथ प्रस्तावपरक तर्क में निश्चित सूत्र चर के कुछ मूल्यों के लिए सही है या नहीं।^[9]

ट्रैवलिंग सेल्समैन

ट्रैवलिंग सेल्समैन समस्या का निर्णय संस्करण एनपी में है। N शहरों के बीच की दूरी के इनपुट आव्युह को देखते हुए, समस्या यह निर्धारित करने की है कि क्या k से कम कुल दूरी वाले सभी शहरों का दौरा करने वाला कोई मार्ग है।

प्रमाण बस शहरों की सूची हो सकती है। फिर बहुपद समय में सत्यापन स्पष्ट रूप से किया जा सकता है। यह बस शहरों के बीच के रास्तों के अनुरूप आव्युह प्रविष्टियाँ जोड़ता है।

गैर-नियतात्मक ट्यूरिंग मशीन इस तरह के मार्ग को निम्नानुसार खोज सकती है:

प्रत्येक शहर का दौरा करने पर यह अगले शहर का अनुमान लगाएगा, जब तक कि यह हर शीर्ष पर नहीं जाता। यदि यह अटक जाता है, तो यह तुरंत रुक जाता है।
अंत में यह सत्यापित करता है कि बिग-ओ नोटेशन (एन) समय में जिस मार्ग को उसने लिया है, उसकी व्यय k से कम है।

प्रत्येक अनुमान को कांटा (प्रणाली कॉल) के रूप में ट्यूरिंग मशीन की नई प्रति के रूप में सोच सकते हैं जिससे आगे के प्रत्येक संभावित पथ का अनुसरण किया जा सके, और यदि कम से कम मशीन k से कम दूरी का मार्ग पाती है, तो वह मशीन इनपुट स्वीकार करती है। (समान रूप से, इसे एकल ट्यूरिंग मशीन के रूप में सोचा जा सकता है जो सदैव सही अनुमान लगाती है)

संभावित दूरियों की सीमा पर द्विआधारी खोज ट्रैवलिंग सेल्समैन की समस्या निर्णय संस्करण को अनुकूलन संस्करण में बदल सकती है, निर्णय संस्करण को बार-बार कॉल करके ( बहुपद संख्या)।^[10]^[8]

सबग्राफ समरूपता

यह निर्धारित करने की सबग्राफ समरूपता समस्या है कि क्या ग्राफ $G$ में सबग्राफ है जो ग्राफ $H$ के लिए आइसोमोर्फिक होता है।^[11]

यह भी देखें

ट्यूरिंग मशीन – Computation model defining an abstract machine

संदर्भ

↑ Ladner, R. E. (1975). "बहुपद समय न्यूनीकरण की संरचना पर". J. ACM. 22: 151–171. doi:10.1145/321864.321877. S2CID 14352974. Corollary 1.1.
↑ ^2.0 ^2.1 Kleinberg, Jon; Tardos, Éva (2006). एल्गोरिथम डिजाइन (2nd ed.). Addison-Wesley. p. 464. ISBN 0-321-37291-3.
↑ Alsuwaiyel, M. H.: Algorithms: Design Techniques and Analysis, p. 283.
↑ William Gasarch (June 2002). "The P=?NP poll" (PDF). SIGACT News. 33 (2): 34–47. doi:10.1145/1052796.1052804. S2CID 18759797. Retrieved 2008-12-29.
↑ Kleinberg, Jon; Tardos, Éva (2006). एल्गोरिथम डिजाइन (2nd ed.). p. 496. ISBN 0-321-37291-3.
↑ "Complexity Zoo:E". Complexity Zoo. Archived from the original on 2020-11-11. Retrieved 23 March 2018.
↑ Lance Fortnow, Pulling Out The Quantumness, December 20, 2005
↑ ^8.0 ^8.1 Wigderson, Avi. "P, NP and mathematics – a computational complexity perspective" (PDF). Retrieved 13 Apr 2021.{{cite web}}: CS1 maint: url-status (link)
↑ Karp, Richard (1972). "मिश्रित समस्याओं के बीच न्यूनीकरण" (PDF). Complexity of Computer Computations: 85–103. doi:10.1007/978-1-4684-2001-2_9. ISBN 978-1-4684-2003-6.
↑ Aaronson, Scott. "P=? NP" (PDF). Retrieved 13 Apr 2021.{{cite web}}: CS1 maint: url-status (link)
↑ Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.

अग्रिम पठन

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 34.2: Polynomial-time verification, pp. 979–983.
Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Sections 7.3–7.5 (The Class NP, NP-completeness, Additional NP-complete Problems), pp. 241–271.
David Harel, Yishai Feldman. Algorithmics: The Spirit of Computing, Addison-Wesley, Reading, MA, 3rd edition, 2004.

बाहरी संबंध

Complexity Zoo: NP
American Scientist primer on traditional and recent complexity theory research: "Accidental Algorithms"

[3] Polynomial time refers to how quickly the number of operations needed by an algorithm, relative to the size of the problem, grows. It is therefore a measure of efficiency of an algorithm.

[5] Under the assumption that P ≠ NP.

[1] Ladner, R. E. (1975). "बहुपद समय न्यूनीकरण की संरचना पर". J. ACM. 22: 151–171. doi:10.1145/321864.321877. S2CID 14352974. Corollary 1.1.

[kleinberg2006-2] 2.0 ^2.1 Kleinberg, Jon; Tardos, Éva (2006). एल्गोरिथम डिजाइन (2nd ed.). Addison-Wesley. p. 464. ISBN 0-321-37291-3.

[4] Alsuwaiyel, M. H.: Algorithms: Design Techniques and Analysis, p. 283.

[poll-6] William Gasarch (June 2002). "The P=?NP poll" (PDF). SIGACT News. 33 (2): 34–47. doi:10.1145/1052796.1052804. S2CID 18759797. Retrieved 2008-12-29.

[kleinberg2006p496-7] Kleinberg, Jon; Tardos, Éva (2006). एल्गोरिथम डिजाइन (2nd ed.). p. 496. ISBN 0-321-37291-3.

[8] "Complexity Zoo:E". Complexity Zoo. Archived from the original on 2020-11-11. Retrieved 23 March 2018.

[9] Lance Fortnow, Pulling Out The Quantumness, December 20, 2005

[:0-10] 8.0 ^8.1 Wigderson, Avi. "P, NP and mathematics – a computational complexity perspective" (PDF). Retrieved 13 Apr 2021.{{cite web}}: CS1 maint: url-status (link)

[11] Karp, Richard (1972). "मिश्रित समस्याओं के बीच न्यूनीकरण" (PDF). Complexity of Computer Computations: 85–103. doi:10.1007/978-1-4684-2001-2_9. ISBN 978-1-4684-2003-6.

[12] Aaronson, Scott. "P=? NP" (PDF). Retrieved 13 Apr 2021.{{cite web}}: CS1 maint: url-status (link)

[13] Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.

[1]

[2]

[Note 1]

[3]

[Note 2]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Line 1: / Line 1: @@
 {{annotated link|ट्यूरिंग मशीन}}
 {{unsolved|अभिकलित्र विज्ञान|<math>\mathsf{P\ \overset{?}{=}\ NP}</math><!-- as of 2022, \overset destroys binary-operator spacings, so they are added here manually -->}}
-[[File:P np np-complete np-hard.svg|thumb|300px|right|[[पी (जटिलता)]], एनपी, एनपी-पूर्ण, और [[ एनपी कठिन |एनपी कठिन]] समुच्चय  समस्याओं के लिए [[यूलर आरेख]]। इस धारणा के अनुसार   कि पी ≠ एनपी, एनपी के अंदर  लेकिन पी और एनपी दोनों के बाहर समस्याओं का अस्तित्व-पूर्ण लेडनर का प्रमेय था।<ref>{{cite journal |first=R. E. |last=Ladner |title=बहुपद समय न्यूनीकरण की संरचना पर|journal=J. ACM |volume=22 |pages=151&ndash;171 |doi=10.1145/321864.321877 |year=1975 |s2cid=14352974 }} Corollary 1.1.</ref>]][[कम्प्यूटेशनल जटिलता सिद्धांत]] में, एनपी (गैर-नियतात्मक बहुपद समय) [[जटिलता वर्ग]] है जिसका उपयोग [[निर्णय समस्या]]ओं को वर्गीकृत करने के लिए किया जाता है। एनपी निर्णय समस्याओं का समुच्चय  [[सेट (गणित)|(गणित)]] है जिसके लिए कम्प्यूटेशनल जटिलता सिद्धांत या समस्या उदाहरण, जहां उत्तर "हां" है, [[नियतात्मक ट्यूरिंग मशीन]] द्वारा बहुपद समय में [[गणितीय प्रमाण]] सत्यापन योग्य है, या वैकल्पिक रूप से समस्याओं का समुच्चय जिसे हल किया जा सकता है गैर नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद समय।<ref name = "kleinberg2006">{{cite book |year=2006 |edition=2nd |title=एल्गोरिथम डिजाइन|url=https://archive.org/details/algorithmdesign0000klei |url-access=registration |first1=Jon |last1=Kleinberg |first2=Éva |last2=Tardos |isbn=0-321-37291-3 |publisher=Addison-Wesley |page=[https://archive.org/details/algorithmdesign0000klei/page/464 464]}}</ref><ref group="Note">''Polynomial time'' refers to how quickly the number of operations needed by an algorithm, relative to the size of the problem, grows. It is therefore a measure of efficiency of an algorithm.</ref>
+[[File:P np np-complete np-hard.svg|thumb|300px|right|[[पी (जटिलता)]], एनपी, एनपी-पूर्ण, और [[ एनपी कठिन |एनपी कठिन]] समुच्चय  समस्याओं के लिए [[यूलर आरेख]]। इस धारणा के अनुसार   कि पी ≠ एनपी, एनपी के अंदर  किन्तु पी और एनपी दोनों के बाहर समस्याओं का अस्तित्व-पूर्ण लेडनर का प्रमेय था।<ref>{{cite journal |first=R. E. |last=Ladner |title=बहुपद समय न्यूनीकरण की संरचना पर|journal=J. ACM |volume=22 |pages=151&ndash;171 |doi=10.1145/321864.321877 |year=1975 |s2cid=14352974 }} Corollary 1.1.</ref>]][[कम्प्यूटेशनल जटिलता सिद्धांत]] में, एनपी (गैर-नियतात्मक बहुपद समय) [[जटिलता वर्ग]] है जिसका उपयोग [[निर्णय समस्या]]ओं को वर्गीकृत करने के लिए किया जाता है। एनपी निर्णय समस्याओं का समुच्चय  [[सेट (गणित)|(गणित)]] है जिसके लिए कम्प्यूटेशनल जटिलता सिद्धांत या समस्या उदाहरण, जहां उत्तर "हां" है, [[नियतात्मक ट्यूरिंग मशीन]] द्वारा बहुपद समय में [[गणितीय प्रमाण]] सत्यापन योग्य है, या वैकल्पिक रूप से समस्याओं का समुच्चय जिसे हल किया जा सकता है गैर नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद समय।<ref name = "kleinberg2006">{{cite book |year=2006 |edition=2nd |title=एल्गोरिथम डिजाइन|url=https://archive.org/details/algorithmdesign0000klei |url-access=registration |first1=Jon |last1=Kleinberg |first2=Éva |last2=Tardos |isbn=0-321-37291-3 |publisher=Addison-Wesley |page=[https://archive.org/details/algorithmdesign0000klei/page/464 464]}}</ref><ref group="Note">''Polynomial time'' refers to how quickly the number of operations needed by an algorithm, relative to the size of the problem, grows. It is therefore a measure of efficiency of an algorithm.</ref>
 एनपी की समतुल्य परिभाषा गैर-नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद समय में सत्यापन योग्य निर्णय समस्याओं का समूह है। यह परिभाषा संक्षिप्त नाम एनपी का आधार है; "[[गैर नियतात्मक एल्गोरिथम]] , बहुपद समय"। ये दो परिभाषाएँ समतुल्य हैं क्योंकि ट्यूरिंग मशीन पर आधारित एल्गोरिथ्म में दो चरण होते हैं, जिनमें से पहले में समाधान के बारे में अनुमान होता है, जो गैर-नियतात्मक तरीके से उत्पन्न होता है, जबकि दूसरे चरण में नियतात्मक एल्गोरिथ्म होता है जो यह सत्यापित करता है कि क्या अनुमान समस्या का समाधान है।<ref>Alsuwaiyel, M. H.: ''Algorithms: Design Techniques and Analysis'', [https://books.google.com/books?id=SPx4iHZEOugC&pg=PA283 p.&nbsp;283].</ref>
-यह देखना आसान है कि जटिलता वर्ग पी (जटिलता) (सभी समस्याओं को हल करने योग्य, निश्चित रूप से, बहुपद समय में) एनपी में समाहित है (समस्याएं जहां बहुपद समय में समाधान सत्यापित किए जा सकते हैं), क्योंकि यदि कोई समस्या बहुपद समय में हल करने योग्य है, फिर समस्या को हल करके बहुपद समय में समाधान भी सत्यापित किया जा सकता है। लेकिन एनपी में और भी कई समस्याएं हैं,<ref group="Note">Under the assumption that P&nbsp;≠&nbsp;NP.</ref> जिनमें से सबसे कठिन को एनपी-पूर्ण समस्याएं कहा जाता है। बहुपद समय में ऐसी समस्या को हल करने वाला एल्गोरिदम बहुपद समय में किसी अन्य एनपी समस्या को हल करने में भी सक्षम है। सबसे महत्वपूर्ण पी बनाम एनपी समस्या | पी बनाम एनपी ("पी = एनपी?") समस्या, पूछती है कि क्या एनपी-पूर्ण, और परिणाम द्वारा, सभी एनपी समस्याओं को हल करने के लिए बहुपद-समय एल्गोरिदम उपस्थित  हैं। यह व्यापक रूप से माना जाता है कि ऐसा नहीं है।<ref name="poll">{{cite journal |author=William Gasarch |author-link=William Gasarch |title=The P=?NP poll |journal=SIGACT News |volume=33 |issue=2 |pages=34–47 |date=June 2002 |url=https://www.cs.umd.edu/~gasarch/papers/poll.pdf |doi=10.1145/1052796.1052804 |s2cid=18759797 |access-date=2008-12-29}}</ref>
+यह देखना आसान है कि जटिलता वर्ग पी (जटिलता) (सभी समस्याओं को हल करने योग्य, निश्चित रूप से, बहुपद समय में) एनपी में समाहित है (समस्याएं जहां बहुपद समय में समाधान सत्यापित किए जा सकते हैं), क्योंकि यदि कोई समस्या बहुपद समय में हल करने योग्य है, फिर समस्या को हल करके बहुपद समय में समाधान भी सत्यापित किया जा सकता है। किन्तु एनपी में और भी कई समस्याएं हैं,<ref group="Note">Under the assumption that P&nbsp;≠&nbsp;NP.</ref> जिनमें से सबसे कठिन को एनपी-पूर्ण समस्याएं कहा जाता है। बहुपद समय में ऐसी समस्या को हल करने वाला एल्गोरिदम बहुपद समय में किसी अन्य एनपी समस्या को हल करने में भी सक्षम है। सबसे महत्वपूर्ण पी बनाम एनपी समस्या | पी बनाम एनपी ("पी = एनपी?") समस्या, पूछती है कि क्या एनपी-पूर्ण, और परिणाम द्वारा, सभी एनपी समस्याओं को हल करने के लिए बहुपद-समय एल्गोरिदम उपस्थित  हैं। यह व्यापक रूप से माना जाता है कि ऐसा नहीं है।<ref name="poll">{{cite journal |author=William Gasarch |author-link=William Gasarch |title=The P=?NP poll |journal=SIGACT News |volume=33 |issue=2 |pages=34–47 |date=June 2002 |url=https://www.cs.umd.edu/~gasarch/papers/poll.pdf |doi=10.1145/1052796.1052804 |s2cid=18759797 |access-date=2008-12-29}}</ref>
 जटिलता वर्ग एनपी जटिलता वर्ग [[सह-एनपी]] से संबंधित है, जिसके लिए बहुपद समय में उत्तर संख्या को सत्यापित नहीं किया जा सकता है। की भी होगी या नहीं {{nobr|NP {{=}} co-NP}} जटिलता सिद्धांत में और उत्कृष्ट प्रश्न है।<ref name="kleinberg2006p496">{{cite book |year=2006 |edition=2nd |title=एल्गोरिथम डिजाइन|url=https://archive.org/details/algorithmdesign0000klei |url-access=registration |first1=Jon |last1=Kleinberg |first2=Éva |last2=Tardos |isbn=0-321-37291-3 |page=[https://archive.org/details/algorithmdesign0000klei/page/496 496]}}</ref>
@@ Line 30: / Line 30: @@
 यह उत्तर देने के लिए कि क्या कुछ पूर्णांक शून्य में जुड़ते हैं, हम एल्गोरिथम बना सकते हैं जो सभी संभावित उपसमुच्चयों को प्राप्त करता है। जैसे-जैसे हम एल्गोरिथम में फीड करने वाले पूर्णांकों की संख्या बड़ी होती जाती है, उपसमुच्चयों की संख्या और गणना समय दोनों तेजी से बढ़ते हैं।
-लेकिन ध्यान दें कि यदि हमें विशेष उपसमुच्चय दिया गया है, तो हम उपसमुच्चय के पूर्णांकों का योग करके कुशलतापूर्वक सत्यापित कर सकते हैं कि उपसमुच्चय का योग शून्य है या नहीं। यदि योग शून्य है, तो वह उपसमुच्चय प्रमाण या [[साक्षी (गणित)]] है, उत्तर हाँ है। एल्गोरिथम जो यह सत्यापित करता है कि किसी दिए गए उप समुच्चय  का योग शून्य है या नहीं, सत्यापनकर्ता है। स्पष्ट रूप से, उपसमुच्चय के पूर्णांकों का योग बहुपद समय में किया जा सकता है, और उपसमुच्चय योग समस्या इसलिए एनपी में है।
+किन्तु ध्यान दें कि यदि हमें विशेष उपसमुच्चय दिया गया है, तो हम उपसमुच्चय के पूर्णांकों का योग करके कुशलतापूर्वक सत्यापित कर सकते हैं कि उपसमुच्चय का योग शून्य है या नहीं। यदि योग शून्य है, तो वह उपसमुच्चय प्रमाण या [[साक्षी (गणित)]] है, उत्तर हाँ है। एल्गोरिथम जो यह सत्यापित करता है कि किसी दिए गए उप समुच्चय  का योग शून्य है या नहीं, सत्यापनकर्ता है। स्पष्ट रूप से, उपसमुच्चय के पूर्णांकों का योग बहुपद समय में किया जा सकता है, और उपसमुच्चय योग समस्या इसलिए एनपी में है।
-उपरोक्त उदाहरण को किसी भी निर्णय समस्या के लिए सामान्यीकृत किया जा सकता है। समस्या के किसी भी उदाहरण I को देखते हुए <math> \Pi </math> और गवाह W, यदि कोई सत्यापनकर्ता V उपस्थित  है, ताकि आदेशित जोड़ी (I, W) को इनपुट के रूप में दिया जाए, तो V बहुपद समय में हाँ लौटाता है यदि गवाह यह सिद्ध  करता है कि उत्तर बहुपद समय में हाँ या नहीं है, तो फिर <math> \Pi </math> एनपी में है।
+उपरोक्त उदाहरण को किसी भी निर्णय समस्या के लिए सामान्यीकृत किया जा सकता है। समस्या के किसी भी उदाहरण I को देखते हुए <math> \Pi </math> और गवाह W, यदि कोई सत्यापनकर्ता V उपस्थित  है, जिससे आदेशित जोड़ी (I, W) को इनपुट के रूप में दिया जाए, तो V बहुपद समय में हाँ लौटाता है यदि गवाह यह सिद्ध  करता है कि उत्तर बहुपद समय में हाँ या नहीं है, तो फिर <math> \Pi </math> एनपी में है।
 इस समस्या का नो-उत्तर संस्करण इस प्रकार कहा गया है: पूर्णांकों का परिमित समुच्चय   दिया गया है, क्या प्रत्येक गैर-खाली उपसमुच्चय में गैर-शून्य योग है? . एनपी की सत्यापनकर्ता-आधारित परिभाषा को बिना किसी उत्तर के लिए कुशल सत्यापनकर्ता की आवश्यकता नहीं होती है। बिना उत्तर वाले सत्यापनकर्ताओं के साथ समस्याओं की श्रेणी को सह-एनपी कहा जाता है। वास्तव में, यह खुला प्रश्न है कि क्या एनपी में सभी समस्याओं के पास बिना किसी उत्तर के सत्यापनकर्ता भी हैं और इस प्रकार सह-एनपी में हैं।
@@ Line 52: / Line 52: @@
 इस संदर्भ में महत्वपूर्ण धारणा एनपी-पूर्ण निर्णय समस्याओं का समुच्चय   है, जो एनपी का उप समुच्चय  है और इसे अनौपचारिक रूप से एनपी में सबसे कठिन समस्याओं के रूप में वर्णित किया जा सकता है। यदि उनमें से "एक" के लिए बहुपद-समय एल्गोरिदम है, तो एनपी में "सभी" समस्याओं के लिए बहुपद-समय एल्गोरिदम है। इस वजह से, और क्योंकि समर्पित शोध किसी भी एनपी-पूर्ण समस्या के लिए बहुपद एल्गोरिदम खोजने में विफल रहा है, बार समस्या एनपी-पूर्ण सिद्ध  हो जाने के बाद, यह व्यापक रूप से संकेत के रूप में माना जाता है कि इस समस्या के लिए बहुपद एल्गोरिदम की संभावना नहीं है अस्तित्व के लिए।
-चूंकि  , व्यावहारिक उपयोगों में, इष्टतम समाधान की तलाश में कम्प्यूटेशनल संसाधनों को खर्च करने के अतिरिक्त , बहुपद समय में अच्छा पर्याप्त (लेकिन संभावित उप-इष्टतम) समाधान अधिकांशतः  पाया जा सकता है। साथ ही, कुछ समस्याओं के वास्तविक जीवन के अनुप्रयोग उनके सैद्धांतिक समकक्षों की तुलना में आसान होते हैं।
+चूंकि  , व्यावहारिक उपयोगों में, इष्टतम समाधान की तलाश में कम्प्यूटेशनल संसाधनों को खर्च करने के अतिरिक्त , बहुपद समय में अच्छा पर्याप्त (किन्तु संभावित उप-इष्टतम) समाधान अधिकांशतः  पाया जा सकता है। साथ ही, कुछ समस्याओं के वास्तविक जीवन के अनुप्रयोग उनके सैद्धांतिक समकक्षों की तुलना में आसान होते हैं।
 == परिभाषाओं की समानता ==
@@ Line 65: / Line 65: @@
 [[Image:Complexity-classes-polynomial.svg|thumb|पी (जटिलता), एनपी (जटिलता), सह-एनपी, [[बीपीपी (जटिलता)]], पी/पॉली, [[पीएच (जटिलता)]], और [[पीएसपीएसीई]] सहित जटिलता वर्गों का समावेश]]एनपी में पी (जटिलता) में सभी समस्याएं सम्मिलित  हैं, क्योंकि कोई भी प्रमाण  को अनदेखा करके और इसे हल करके समस्या के किसी भी उदाहरण को सत्यापित कर सकता है। एनपी पीएसपीएसीई में निहित है - यह दिखाने के लिए, यह पीएसपीएसीई मशीन बनाने के लिए पर्याप्त है जो सभी प्रमाण  तारों पर लूप करता है और प्रत्येक को बहुपद-समय सत्यापनकर्ता को खिलाता है। चूंकि बहुपद-समय मशीन बहुपद रूप से केवल कई बिट्स पढ़ सकती है, यह बहुपद स्थान से अधिक का उपयोग नहीं कर सकती है, न ही यह बहुपद स्थान से अधिक पर कब्जा करने वाली प्रमाण  स्ट्रिंग पढ़ सकती है (इसलिए हमें इससे अधिक प्रमाण  पर विचार करने की ज़रूरत नहीं है)। एनपी [[EXPTIME|एक्स्प्तिमे]] में भी समाहित है, क्योंकि ही एल्गोरिथ्म घातीय समय में संचालित होता है।
-सह-एनपी में वे समस्याएं सम्मिलित  हैं जिनके पास बिना किसी उदाहरण के सरल प्रमाण है, जिसे कभी-कभी प्रति उदाहरण कहा जाता है। उदाहरण के लिए, [[प्रारंभिक परीक्षण]] सह-एनपी में मामूली रूप से निहित है, क्योंकि कोई केवल गैर-कारक कारक की आपूर्ति करके पूर्णांक की प्राथमिकता को अस्वीकार कर सकता है। एनपी और सह-एनपी मिलकर [[बहुपद पदानुक्रम]] में पहला स्तर बनाते हैं, केवल पी से अधिक।
+सह-एनपी में वे समस्याएं सम्मिलित  हैं जिनके पास बिना किसी उदाहरण के सरल प्रमाण है, जिसे कभी-कभी प्रति उदाहरण कहा जाता है। उदाहरण के लिए, [[प्रारंभिक परीक्षण]] सह-एनपी में सामान्य   रूप से निहित है, क्योंकि कोई केवल गैर-कारक कारक की आपूर्ति करके पूर्णांक की प्राथमिकता को अस्वीकार कर सकता है। एनपी और सह-एनपी मिलकर [[बहुपद पदानुक्रम]] में पहला स्तर बनाते हैं, केवल पी से अधिक।
 एनपी को केवल नियतात्मक मशीनों का उपयोग करके परिभाषित किया गया है। यदि हम सत्यापनकर्ता को संभाव्य होने की अनुमति देते हैं (चूंकि  , यह बीपीपी मशीन नहीं है<ref>{{cite web |url=https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#existsbpp |title=Complexity Zoo:E  |website=Complexity Zoo |access-date=23 March 2018 |archive-url=https://web.archive.org/web/20201111211915/https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E |archive-date=2020-11-11 |url-status=dead}}</ref>), हम आर्थर-मर्लिन प्रोटोकॉल का उपयोग करके कक्षा एमए को हल करने योग्य पाते हैं, जिसमें आर्थर से मर्लिन तक कोई संचार नहीं है।
@@ Line 76: / Line 76: @@
 == अन्य लक्षण ==
-[[वर्णनात्मक जटिलता सिद्धांत]] के संदर्भ में, एनपी अस्तित्वगत दूसरे क्रम के तर्क (फागिन के प्रमेय) द्वारा परिभाषित भाषाओं के समुच्चय   से सटीक रूप से मेल खाता है।
+[[वर्णनात्मक जटिलता सिद्धांत]] के संदर्भ में, एनपी अस्तित्वगत दूसरे क्रम के तर्क (फागिन के प्रमेय) द्वारा परिभाषित भाषाओं के समुच्चय   से स्पष्ट  रूप से मेल खाता है।
 एनपी को बहुत ही सरल प्रकार के [[इंटरैक्टिव प्रूफ सिस्टम|इंटरैक्टिव प्रूफ]] प्रणाली के रूप में देखा जा सकता है, जहां प्रोवर प्रूफ सर्टिफिकेट के साथ आता है और सत्यापनकर्ता नियतात्मक बहुपद-टाइम मशीन है जो इसकी जांच करता है। यह पूरा हो गया है क्योंकि सही प्रूफ स्ट्रिंग यदि  है तो इसे स्वीकार कर लेगा, और यह ध्वनि है क्योंकि यदि  कोई स्वीकार्य प्रूफ स्ट्रिंग नहीं है तो सत्यापनकर्ता स्वीकार नहीं कर सकता है।
-जटिलता सिद्धांत का प्रमुख परिणाम यह है कि एनपी को संभावित रूप से जांच योग्य प्रमाण द्वारा हल करने योग्य समस्याओं के रूप में वर्णित किया जा सकता है जहां सत्यापनकर्ता ओ (लॉग एन) यादृच्छिक बिट्स का उपयोग करता है और प्रमाण  स्ट्रिंग (वर्ग 'पीसीपी' वर्ग) के केवल बिट्स की निरंतर संख्या की जांच करता है। लॉग एन, 1))। अधिक अनौपचारिक रूप से, इसका मतलब यह है कि ऊपर वर्णित एनपी सत्यापनकर्ता को के साथ प्रतिस्थापित किया जा सकता है जो प्रूफ स्ट्रिंग में कुछ स्थानों पर स्पॉट-चेक करता है, और सीमित संख्या में सिक्का फ़्लिप का उपयोग करके उच्च संभावना के साथ सही उत्तर निर्धारित कर सकता है। यह सन्निकटन एल्गोरिदम की कठोरता के बारे में कई परिणाम सिद्ध करने की अनुमति देता है।
+जटिलता सिद्धांत का प्रमुख परिणाम यह है कि एनपी को संभावित रूप से जांच योग्य प्रमाण द्वारा हल करने योग्य समस्याओं के रूप में वर्णित किया जा सकता है जहां सत्यापनकर्ता ओ (लॉग एन) यादृच्छिक बिट्स का उपयोग करता है और प्रमाण  स्ट्रिंग (वर्ग 'पीसीपी' वर्ग) के केवल बिट्स की निरंतर संख्या की जांच करता है। लॉग एन, 1))। अधिक अनौपचारिक रूप से, इसका कारण यह है कि ऊपर वर्णित एनपी सत्यापनकर्ता को के साथ प्रतिस्थापित किया जा सकता है जो प्रूफ स्ट्रिंग में कुछ स्थानों पर स्पॉट-चेक करता है, और सीमित संख्या में सिक्का फ़्लिप का उपयोग करके उच्च संभावना के साथ सही उत्तर निर्धारित कर सकता है। यह सन्निकटन एल्गोरिदम की कठोरता के बारे में कई परिणाम सिद्ध करने की अनुमति देता है।
 == उदाहरण ==
@@ Line 113: / Line 113: @@
 * प्रत्येक शहर का दौरा करने पर यह अगले शहर का अनुमान लगाएगा, जब तक कि यह हर शीर्ष पर नहीं जाता। यदि  यह अटक जाता है, तो यह तुरंत रुक जाता है।
-* अंत में यह सत्यापित करता है कि [[बिग-ओ नोटेशन]] (एन) समय में जिस मार्ग को उसने लिया है, उसकी लागत k से कम है।
+* अंत में यह सत्यापित करता है कि [[बिग-ओ नोटेशन]] (एन) समय में जिस मार्ग को उसने लिया है, उसकी व्यय  k से कम है।
-प्रत्येक अनुमान को [[ कांटा (सिस्टम कॉल) |कांटा (प्रणाली कॉल)]] के रूप में ट्यूरिंग मशीन की नई प्रति के रूप में सोच सकते हैं ताकि आगे के प्रत्येक संभावित पथ का अनुसरण किया जा सके, और यदि कम से कम मशीन k से कम दूरी का मार्ग पाती है, तो वह मशीन इनपुट स्वीकार करती है। (समान रूप से, इसे एकल ट्यूरिंग मशीन के रूप में सोचा जा सकता है जो सदैव  सही अनुमान लगाती है)
+प्रत्येक अनुमान को [[ कांटा (सिस्टम कॉल) |कांटा (प्रणाली कॉल)]] के रूप में ट्यूरिंग मशीन की नई प्रति के रूप में सोच सकते हैं जिससे आगे के प्रत्येक संभावित पथ का अनुसरण किया जा सके, और यदि कम से कम मशीन k से कम दूरी का मार्ग पाती है, तो वह मशीन इनपुट स्वीकार करती है। (समान रूप से, इसे एकल ट्यूरिंग मशीन के रूप में सोचा जा सकता है जो सदैव  सही अनुमान लगाती है)
 संभावित दूरियों की सीमा पर [[द्विआधारी खोज]] [[ट्रैवलिंग सेल्समैन की समस्या]] निर्णय संस्करण को अनुकूलन संस्करण में बदल सकती है, निर्णय संस्करण को बार-बार कॉल करके ( बहुपद संख्या)।<ref>{{Cite web|last=Aaronson|first=Scott|title=P=? NP|url=https://www.scottaaronson.com/papers/pnp.pdf|url-status=live|access-date=13 Apr 2021}}</ref><ref name=":0">{{Cite web|last=Wigderson|first=Avi|title=P, NP and mathematics – a computational complexity perspective|url=https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W06/w06.pdf|url-status=live|access-date=13 Apr 2021}}</ref>

v t e Important complexity classes (more)
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

Anonymous

Search

एनपी (जटिलता): Difference between revisions

Namespaces

More

Page actions

Revision as of 11:30, 25 May 2023

Contents

औपचारिक परिभाषा