एनपी (जटिलता)

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

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

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

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

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

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

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

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

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

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

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

${\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$ एनपी में है।

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

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

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

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

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

गुण

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

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

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

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

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

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

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

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

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

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

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

File:Complexity-classes-polynomial.svg

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

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

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

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

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

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

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

अन्य लक्षण

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

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

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

उदाहरण

पी

पी (जटिलता) में सभी समस्याएं, निरूपित $\mathsf{P}\subseteq <!--\; \subseteq \; -->\mathsf{N}$