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

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

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

निर्णय की समस्या औपचारिक भाषा से जुड़ी हो सकती है $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.

श्रेणी:कम्प्यूटेशनल समस्याएँ