जटिलता सिद्धांत: P, NP व NP-पूर्णता

GATE के उधार लिए कलनविधि अध्याय (अनंतस्पर्शी जटिलता, अभिकल्प-तकनीकें, ग्राफ कलनविधियाँ) जटिलता-सिद्धांत स्वयं तक नहीं पहुँचते। NET की इकाई 7, P/NP वर्ग समस्याओं व NP-पूर्णता/न्यूनन को अपने ही प्रकरण के रूप में नामित करती है, जिसे यह अध्याय सावधानी से व सही ढंग से आधारित करता है — यह ठीक वैसा तकनीकी रूप से यथार्थ दावा है, इकाई 8 के स्वचालित-सिद्धांत दावों की भाँति, जिसे कभी हाथ हिलाकर नहीं टाला जाना चाहिए।

वर्ग P व NP

P निर्णय-समस्याओं (हाँ/नहीं उत्तर) का वह वर्ग है जो निर्धारणात्मक कलनविधि से निवेश-आकार में बहुपद निकृष्टतम-स्थिति समय में हल करने योग्य हैं — अनौपचारिक रूप से, 'दक्षतापूर्वक हल करने योग्य'। NP वह वर्ग है जहाँ प्रस्तावित हाँ-उत्तर (एक प्रमाणपत्र/साक्षी) को बहुपद समय में सत्यापित किया जा सकता है, भले ही सर्वप्रथम उस प्रमाणपत्र को खोजने हेतु कोई बहुपद-समय कलनविधि ज्ञात न हो। P की हर समस्या NP में भी है (यदि आप इसे बहुपद समय में हल कर सकते हैं, तो आप निश्चित रूप से इसे स्वयं हल करके प्रस्तावित उत्तर को बहुपद समय में सत्यापित कर सकते हैं) — अतः P ⊆ NP सिद्ध है; क्या P = NP है (क्या हर दक्षतापूर्वक-सत्यापन-योग्य समस्या दक्षतापूर्वक-हल-योग्य भी है) कंप्यूटर विज्ञान की सर्वाधिक प्रसिद्ध अनसुलझी समस्या है, अनिश्चित।

⚠️ NP का अर्थ 'गैर-बहुपद' नहीं है
यह सबसे आम गलत-पठन है। NP का अर्थ अनिर्धारणात्मक बहुपद (Nondeterministic Polynomial) है — एक अनिर्धारणात्मक ट्यूरिंग मशीन जो प्रमाणपत्र का 'अनुमान' लगा सके व उसे बहुपद समय में सत्यापित कर सके, या समतुल्यतः (व्यवहार में वस्तुतः प्रयुक्त परिभाषा), प्रस्तावित प्रमाणपत्र के बहुपद-समय सत्यापन से परिभाषित वर्ग। NP समस्याएँ बहुपद समय में हल-न-होने योग्य ज्ञात नहीं हैं; उनमें से कुछ (P की सभी) प्रदर्श रूप से बहुपद समय में हल-योग्य हैं। जो अनिश्चित है वह यह है कि क्या सम्पूर्ण NP है।

NP-पूर्णता व बहुपद-समय न्यूनन

समस्या X NP-कठिन है यदि NP की हर समस्या को X में बहुपद-समय न्यून किया जा सके — अनौपचारिक रूप से, X 'NP में सब कुछ जितनी कम-से-कम कठिन' है, क्योंकि X हेतु बहुपद-समय कलनविधि हर NP समस्या हेतु बहुपद-समय कलनविधि दे देगी। समस्या X NP-पूर्ण है यदि यह NP-कठिन तथा स्वयं NP में दोनों हो — 'सर्वाधिक कठिन समस्याएँ जो फिर भी सत्यापन-योग्य हैं', और यही ठीक वे हैं जिनमें से एक हेतु भी बहुपद-समय कलनविधि सभी हेतु P = NP सिद्ध कर देगी, क्योंकि NP-पूर्ण समस्याएँ सभी एक-दूसरे में बहुपद-समय न्यून करने योग्य हैं। कुक प्रमेय (1971) ने पहली NP-पूर्ण समस्या — बूलियन संतुष्यता (SAT) — सिद्ध की, यह स्थापित करते हुए कि NP-पूर्ण समस्याएँ बिल्कुल विद्यमान हैं; हर बाद का NP-पूर्णता-प्रमाण किसी ज्ञात NP-पूर्ण समस्या को नए प्रत्याशी में न्यून करता है (या प्रत्याशी को किसी ज्ञात में), उस एकल आधार से बाहर की ओर निर्माण करते हुए।

मानक NP-पूर्ण समस्याएँ व वे कैसे संबंधित हैं
समस्याकथन
SAT / 3-SATबूलियन सूत्र (3-SAT में: प्रति उपवाक्य 3 शाब्दिकों सहित संयोजी सामान्य रूप में) दिया है, क्या इसके चरों को सत्य/असत्य के किसी नियतन से पूरा सूत्र सत्य हो जाता है?
शीर्ष-आवरणक्या ग्राफ में अधिकतम k शीर्षों का ऐसा समुच्चय है जो हर कोर को स्पर्श करे?
हैमिल्टन चक्रक्या ग्राफ में ऐसा चक्र है जो हर शीर्ष ठीक एक बार देखे?
0/1 नैपसैक (निर्णय संस्करण)क्या भार-सीमा के भीतर कम-से-कम लक्ष्य मान V तक पहुँचने हेतु वस्तुएँ चुनी जा सकती हैं?

प्रश्न के आकार से NP-पूर्णता पहचानना

🧠 प्रश्न के विषय से नहीं, आकार से NP-पूर्णता पहचानें
अनेक NP-पूर्ण समस्याओं के सरल, बहुपद-समय चचेरे भाई हैं जो लगभग समान लगते हैं — जाल दोनों को भ्रमित करने में है। लघुतम-पथ समस्या P में है (डिजस्ट्रा, अऋणात्मक भारों हेतु); दीर्घतम सरल पथ समस्या NP-कठिन है। आयलर परिपथ समस्या (हर कोर एक बार) P में है, सादी कोटि-सम-विषमता जाँच से निर्णेय; हैमिल्टन चक्र समस्या (हर शीर्ष एक बार) NP-पूर्ण है, बिना किसी ज्ञात सम-विषमता-शैली लघु-मार्ग के। 2-SAT (प्रति उपवाक्य अधिकतम 2 शाब्दिक) P में है; 3-SAT NP-पूर्ण है। ठीक कौन-सा रूपांतर पूछा गया है यह पढ़ना, केवल विषय-क्षेत्र नहीं, इन प्रश्नों को अलग करता है।

NP-पूर्ण हुए बिना NP-कठिन, व साध्य बनाम असाध्य

समस्या NP-पूर्ण हुए बिना NP-कठिन हो सकती है यदि यह स्वयं NP में न हो — सामान्यतः इसलिए कि यह निर्णय-समस्या ही नहीं है, या प्रस्तावित हल का सत्यापन बहुपद समय में संभव ज्ञात नहीं। हाल्टिंग समस्या (इकाई 8 की अभिकलन सिद्धांत सामग्री में ढकी) इस परिभाषा से NP-कठिन है पर NP-पूर्ण नहीं, क्योंकि यह बिल्कुल निर्णेय ही नहीं — कोई कलनविधि, बहुपद हो या न हो, इसे सामान्यतः हल नहीं करती, अतः यह NP में किसी भी वस्तु से केवल कठिनतम-NP-समस्या जितनी कठिन होने के बजाय कड़ाई से कठिनतर है। यात्रा-विक्रेता समस्या अपने अनुकूलन रूप में ('सबसे छोटा दौरा खोजें') NP-कठिन है पर, निर्णय के बजाय अनुकूलन समस्या होने से, स्वयं NP की सदस्य नहीं — इसका निर्णय संस्करण ('क्या लंबाई ≤ k का दौरा है?') वही है जो वस्तुतः NP-पूर्ण है।

  • साध्य अनौपचारिक रूप से 'बहुपद समय में हल-योग्य' (P) का अर्थ रखता है; असाध्य अनौपचारिक रूप से 'कोई ज्ञात बहुपद-समय कलनविधि विद्यमान नहीं' — NP-पूर्ण समस्याएँ (मानी गई) असाध्य समस्याओं के मानक उदाहरण हैं, क्योंकि किसी एक हेतु भी बहुपद-समय कलनविधि P व NP को एक साथ ढहा देगी।
  • व्यवहार में, पहचाने जाने पर NP-पूर्ण समस्या त्यागी नहीं जाती — घातांकी-निकृष्टतम-स्थिति कलनविधियाँ (शाखा-व-परिबंध, सबल छंटाई सहित बैकट्रैकिंग) व्यवहार में उत्पन्न वास्तविक दृष्टांतों पर फिर भी पर्याप्त तेज़ हो सकती हैं, व सन्निकटन कलनविधियाँ (अगले अध्याय में ढकी) बहुपद समय में गणना-योग्य सिद्ध रूप से-इष्टतम-से-परिबद्ध-दूरी वाले उत्तर के बदले सटीकता का व्यापार करती हैं।

मुख्य बिंदु

  • P दक्षतापूर्वक हल-योग्य है; NP दक्षतापूर्वक सत्यापन-योग्य है (प्रस्तावित प्रमाणपत्र बहुपद समय में जाँचा गया) — P ⊆ NP सिद्ध है, P = NP अनिश्चित है।
  • NP का अर्थ 'अनिर्धारणात्मक बहुपद' है, 'गैर-बहुपद' नहीं — मानक गलत-पठन।
  • समस्या NP-पूर्ण है यदि यह NP-कठिन तथा NP में दोनों हो; NP-पूर्ण समस्याएँ सभी एक-दूसरे में बहुपद-समय न्यून करने योग्य हैं, अतः एक हेतु तेज़ कलनविधि सभी को हल कर देती है।
  • अनेक NP-पूर्ण समस्याओं के सरल बहुपद चचेरे भाई हैं जो समान लगते हैं (हैमिल्टन बनाम आयलर चक्र, 3-SAT बनाम 2-SAT, लघुतम बनाम दीर्घतम पथ) — ठीक रूपांतर पढ़ें।
  • हाल्टिंग समस्या NP-कठिन है पर NP-पूर्ण नहीं क्योंकि यह निर्णेय ही नहीं; TSP का अनुकूलन रूप NP-कठिन है पर स्वयं NP में नहीं, इसके निर्णय रूप के विपरीत।

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. NP का अर्थ है:

    1. अनिर्धारणात्मक बहुपद
    2. गैर-बहुपद
    3. कभी न सिद्ध होने योग्य
    4. नई प्रोग्रामिंग
    उत्तर देखें

    उत्तर: A — अनिर्धारणात्मक बहुपद

    NP अनिर्धारणात्मक बहुपद है — उन समस्याओं का वर्ग जिनके प्रस्तावित हाँ-प्रमाणपत्र बहुपद समय में सत्यापन-योग्य हैं — यह दावा नहीं कि इन समस्याओं को बहुपद से अधिक समय चाहिए।

  2. P की हर समस्या NP में भी है क्योंकि:

    1. यदि इसे बहुपद समय में हल किया जा सकता है, तो प्रस्तावित उत्तर को स्वयं हल करके निश्चित रूप से बहुपद समय में सत्यापित किया जा सकता है
    2. P व NP असंबद्ध समुच्चय हैं
    3. NP, P का उपसमुच्चय है
    4. P की कोई समस्या कभी सत्यापित नहीं की जा सकती
    उत्तर देखें

    उत्तर: A — यदि इसे बहुपद समय में हल किया जा सकता है, तो प्रस्तावित उत्तर को स्वयं हल करके निश्चित रूप से बहुपद समय में सत्यापित किया जा सकता है

    बहुपद समय में स्वयं समस्या हल करना ही उसके किसी प्रस्तावित उत्तर को सत्यापित करने का बहुपद-समय तरीका है, जो ठीक वही तर्क है जो P ⊆ NP स्थापित करता है।

  3. समस्या NP-पूर्ण है यदि यह:

    1. NP-कठिन तथा स्वयं NP की सदस्य दोनों
    2. NP-कठिन पर NP में कभी नहीं
    3. P में पर NP में कभी नहीं
    4. अनिर्णेय
    उत्तर देखें

    उत्तर: A — NP-कठिन तथा स्वयं NP की सदस्य दोनों

    NP-पूर्णता को दोनों शर्तें साथ चाहिए — हर NP समस्या जितना कम-से-कम कठिन होना तथा स्वयं बहुपद समय में सत्यापन-योग्य होना — इसीलिए NP-पूर्ण समस्याएँ सभी एक-दूसरे में बहुपद-समय न्यून करने योग्य हैं।

  4. हैमिल्टन चक्र समस्या (हर शीर्ष ठीक एक बार देखें) NP-पूर्ण है, जबकि आयलर परिपथ समस्या (हर कोर ठीक एक बार चलें) P में है। इसका सर्वोत्तम स्पष्टीकरण है:

    1. आयलर के पास स्वच्छ कोटि-सम-विषमता अभिलक्षण है जिसका हैमिल्टन चक्रों हेतु कोई ज्ञात समानांतर नहीं
    2. दोनों समस्याएँ वस्तुतः समान हैं
    3. आयलर हैमिल्टन से कठिन है
    4. किसी भी समस्या को कभी हल नहीं किया जा सकता
    उत्तर देखें

    उत्तर: A — आयलर के पास स्वच्छ कोटि-सम-विषमता अभिलक्षण है जिसका हैमिल्टन चक्रों हेतु कोई ज्ञात समानांतर नहीं

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

  5. हाल्टिंग समस्या NP-कठिन है पर NP-पूर्ण नहीं है क्योंकि:

    1. यह निर्णेय ही नहीं, अतः यह स्वयं NP की सदस्य नहीं है
    2. यह वस्तुतः P में है
    3. NP-कठिन व NP-पूर्ण ठीक पर्यायवाची हैं
    4. इसे कभी कठिन सिद्ध नहीं किया गया
    उत्तर देखें

    उत्तर: A — यह निर्णेय ही नहीं, अतः यह स्वयं NP की सदस्य नहीं है

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

  6. निम्नलिखित में कौन मानक NP-पूर्ण समस्याएँ हैं? (एक से अधिक विकल्प सही हो सकते हैं।)

    1. 3-SAT
    2. शीर्ष-आवरण
    3. हैमिल्टन चक्र
    4. अऋणात्मक भारों सहित एकल-स्रोत लघुतम पथ
    उत्तर देखें

    उत्तर: A — 3-SAT; B — शीर्ष-आवरण; C — हैमिल्टन चक्र

    3-SAT, शीर्ष-आवरण व हैमिल्टन चक्र मानक, पाठ्यपुस्तक NP-पूर्ण समस्याएँ हैं; अऋणात्मक भारों सहित एकल-स्रोत लघुतम पथ P में है, डिजस्ट्रा कलनविधि से दक्षतापूर्वक हल।

  7. उस प्रमेय (1971) का नाम बताइए जिसने पहली ज्ञात NP-पूर्ण समस्या, अर्थात् बूलियन संतुष्यता (SAT), स्थापित की।

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: Cook's theorem

    कुक प्रमेय (लेविन द्वारा भी स्वतंत्र रूप से सिद्ध, इसीलिए प्रायः कुक-लेविन प्रमेय कहा जाता है) ने NP की परिभाषा से सीधे SAT को NP-पूर्ण सिद्ध किया, हर बाद के NP-पूर्णता-प्रमाण को न्यूनन हेतु उसका आरंभिक आधार देते हुए।

  8. यात्रा-विक्रेता समस्या अपने अनुकूलन रूप ('सबसे छोटा दौरा खोजें') में है:

    1. NP-कठिन, पर स्वयं NP की सदस्य नहीं क्योंकि यह निर्णय-समस्या नहीं है
    2. P में
    3. स्थिर समय में निर्णेय
    4. अपने ही निर्णय-संस्करण के समान
    उत्तर देखें

    उत्तर: A — NP-कठिन, पर स्वयं NP की सदस्य नहीं क्योंकि यह निर्णय-समस्या नहीं है

    केवल निर्णय संस्करण ('क्या लंबाई ≤ k का दौरा है?') NP की सदस्य हो सकता है, क्योंकि NP-सदस्यता को सत्यापित करने योग्य हाँ/नहीं प्रमाणपत्र चाहिए; अनुकूलन संस्करण NP-कठिन है (कम-से-कम उतना कठिन) पर स्वयं NP के भीतर वर्गीकृत नहीं।