एनपी-समतुल्य

कम्प्यूटेरीकृत जटिलता सिद्धांत में, जटिलता वर्ग एनपी-समतुल्य फलन वाली समस्याओं का समुच्चय है, जो एनपी-सरलता और एनपी जटिलता दोनों पर निर्भर हैं। इस प्रकार एनपी-समतुल्य फलन समस्याओं के लिए एनपी-पूर्णतः का एनालॉग है।

उदाहरण के लिए यह समस्या FIND-SUBSET-SUM NP के समतुल्य है। इस प्रकार के पूर्णांकों के समुच्चय को देखते हुए FIND-SUBSET-SUM पूर्णांकों के कुछ गैर-रिक्त उपसमुच्चय को खोजने की समस्या है, जो शून्य तक जुड़ जाता है, या यदि ऐसा कोई उपसमुच्चय नहीं है, तो रिक्त समुच्चय लौटाता है। यह अनुकूलन समस्या, निर्णय समस्या, उपसमुच्चय योग समस्या SUBSET-SUM के समान है। जो पूर्णांकों के समुच्चय को देखते हुए SUBSET-SUM का पता लगाने के लिए आने वाली समस्या को दर्शाता है, इसका अर्थ यह हैं कि क्या शून्य का योग करने वाला कोई उपसमुच्चय इसमें उपस्थित है। उपसमुच्चय-एसयूएम एनपी-पूर्ण है।

यह दिखाने के लिए कि FIND-SUBSET-SUM NP-समतुल्य है, हमें यह दिखाना होगा कि यह NP-जटिल और NP-सरल दोनों प्रकार के है।

स्पष्टतः यह एनपी-जटिल है। यदि हमारे पास ब्लैक बॉक्स (सिस्टम) होता जो इस इकाई समय में FIND-SUBSET-SUM को हल करता हैं, तो SUBSET-SUM को हल करना सरल हो जाता हैं। इस प्रकार बस ब्लैक बॉक्स से उस उपसमुच्चय को सर्च करने के लिए काॅल करते हैं, जिसका योग सामान्य रूप से शून्य होता है, इसके पश्चात पुनः यह देखा जाता हैं कि इन जांचों कि क्या उसने कोई गैर-रिक्त समुच्चय रिटर्न करता हैं।

यह एनपी-सरल भी है। यदि हमारे पास ब्लैक बॉक्स होता जो इकाई समय में SUBSET-SUM को हल करता है, तो हम इसका उपयोग FIND-SUBSET-SUM को हल करने के लिए इसका उपयोग करते थे। यदि यह गलत मान रिटर्न करता है, तो हम तुरंत रिक्त समुच्चय लौटा देते हैं। अन्यथा हम क्रम से प्रत्येक तत्व पर जाते हैं और उसे हटा देते हैं, इसका अर्थ यह हैं कि SUBSET-SUM को हटाने के बाद भी यह सही मान लौटाता हैं। इस बार जब हम प्रत्येक तत्व का को देखते हैं, तो हम उत्तर को सत्य से असत्य में परिवर्तित किए बिना किसी भी तत्व को नहीं हटा पाएंगे, इस बिंदु पर मूल तत्वों के शेष उपसमुच्चय का योग शून्य होना चाहिए। इसके लिए हमें यह ध्यान देने की आवश्यकता है कि बाद में इन तत्वों को हटाने से इस तथ्य में कोई परिवर्तन नहीं आता है, इसका अर्थ यह है कि इसके पहले वाले तत्व को हटाने से उत्तर सही से गलत में परिवर्तित किया जाता है। सोर्सकोड के अनुसार:

function FIND-SUBSET-SUM(set S)
    if not(SUBSET-SUM(S))
        return {}
    for each x in S
        if SUBSET-SUM(S – {x})
            S := S – {x}
    return S

एक अन्य प्रसिद्ध एनपी-समतुल्य समस्या ट्रैवलिंग सेल्समैन की समस्या को प्रदर्शित करते हैं।

स्पष्टीकरण

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

संदर्भ

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