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

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

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

एक डिसीजन प्रॉब्लम एक औपचारिक भाषा $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.

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