प्रॉमिस प्रॉब्लम

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

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

इसी प्रकार डिसीजन प्रॉब्लम औपचारिक भाषा $L\subseteq \{0,1\}^{*}$ से जुड़ी हो सकती है, जहां प्रॉब्लम $L$ में सभी इनपुट को एक्सेप्ट करना और इसके अतिरिक्त $L$ में नहीं, अपितु सभी इनपुट को रिजैक्ट करना भी है। प्रॉमिस प्रॉब्लम के लिए, दो लैंग्वेज हैं, $L_{\text{YES}}$ और $L_{\text{NO}}$, जो डिसजोइन्ट होना चाहिए, जिसका अर्थ है $L_{\text{YES}}\cap L_{\text{NO}}=\varnothing$, जैसे कि $L_{\text{YES}}$ में सभी इनपुट को एक्सेप्ट किया जाना चाहिए और $L_{\text{NO}}$ में सभी इनपुट रिजैक्ट कर दिया जाना चाहिए, समुच्चय $L_{\text{YES}}\cup L_{\text{NO}}$ को प्रॉमिस कहा जाता है। यदि इनपुट प्रॉमिस से संबंधित नहीं है तो आउटपुट पर इसकी कोई आवश्यकता नहीं होती है। यदि प्रॉमिस $\{0,1\}^{*}$ के समतुल्य है, तो यह भी डिसीजन प्रॉब्लम है, और प्रॉमिस को ट्रिविअल कहा जाता है।

इंस्टैंस

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

यह भी देखें

• कम्प्यूटेशनल प्रॉब्लम
• डिसीजन प्रॉब्लम
• अनुकूलन प्रॉब्लम
• खोज प्रॉब्लम
• गिनती की प्रॉब्लम (कॉम्पलेक्सिटी)
• कार्य प्रॉब्लम
• टीएफएनपी

संदर्भ

सर्वेक्षण

• Goldreich, Oded (2006). "On Promise Problems (a survey)". सैद्धांतिक कंप्यूटर विज्ञान: शिमोन इवन की स्मृति में निबंध. LNCS. Vol. 3895. pp. 254–290. doi:10.1007/11685654_12.
• Sahai, A.; Vadhan, S.P. (1997). "सांख्यिकीय शून्य-ज्ञान के लिए एक पूर्ण वादा समस्या". FOCS 1997. pp. 448–457. CiteSeerX 10.1.1.34.6920. doi:10.1109/SFCS.1997.646133.
• Even, Shimon; Selman, Alan L.; Yacobi, Yacov (1984). "सार्वजनिक-कुंजी क्रिप्टोग्राफी के अनुप्रयोगों के साथ वादा समस्याओं की जटिलता". Information and Control. 61 (2): 159–173. doi:10.1016/S0019-9958(84)80056-X.

श्रेणी:कम्प्यूटेशनल प्रॉब्लम्स