एनपी-समतुल्य
कम्प्यूटेशनल जटिलता सिद्धांत में, जटिलता वर्ग एनपी-समतुल्य फ़ंक्शन समस्याओं का सेट है जो एनपी-आसान और एनपी कठिन दोनों हैं।[1] एनपी-समतुल्य फ़ंक्शन समस्याओं के लिए एनपी-पूर्ण का एनालॉग है।
उदाहरण के लिए, समस्या 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 उसे हटाने के बाद भी सत्य लौटाए। एक बार जब हम प्रत्येक तत्व का दौरा कर लेते हैं, तो हम उत्तर को सत्य से असत्य में बदले बिना किसी भी तत्व को नहीं हटा पाएंगे; इस बिंदु पर मूल तत्वों के शेष उपसमुच्चय का योग शून्य होना चाहिए। इसके लिए हमें यह ध्यान देने की आवश्यकता है कि बाद में तत्वों को हटाने से इस तथ्य में कोई बदलाव नहीं आता है कि पहले वाले तत्व को हटाने से उत्तर सही से गलत में बदल जाता है। छद्मकोड में:
'फ़ंक्शन' ढूँढें-सबसेट-योग (सेट एस)
'यदि' 'नहीं'(उपसेट-योग(एस))
'वापस करना' {}
'प्रत्येक' x 'में' एस के लिए
'अगर' सबसेट-योग(एस - {x})
एस := एस - {x}
'वापसी' एस
एक अन्य प्रसिद्ध एनपी-समतुल्य समस्या ट्रैवलिंग सेल्समैन की समस्या है।
स्पष्टीकरण
इस संदर्भ में एनपी का मतलब एनपी (जटिलता) है।
बूलियन फ़ंक्शन के एनपी-समतुल्य वर्ग भी हैं, जहां एनपी का अर्थ निषेध और क्रमपरिवर्तन है।
[2]
टिप्पणियाँ
- ↑ Garey & Johnson (1979), p. 117, 120.
- ↑ See e.g. the sequence A000616 in the OEIS. Often used in the context of NPN-equivalence classes. (E.g. in A New Pairwise NPN Boolean Matching Algorithm....)
