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

ट्यूरिंग मशीन – 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।

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

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

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

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

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

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

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

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

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

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

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

अन्य लक्षण

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

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

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

उदाहरण

पी

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

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

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

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

Main article: एनपी-पूर्ण समस्याओं की सूची

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

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

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

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

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

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

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

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

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

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

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

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

यह भी देखें

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

अग्रिम पठन

• 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"