प्रॉमिस प्रॉब्लम: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Type of computational problem}} | {{Short description|Type of computational problem}} | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कॉम्पलेक्सिटी थ्योरी]] में, '''प्रॉमिस प्रॉब्लम''' [[निर्णय समस्या|डिसीजन प्रॉब्लम]] का सामान्यीकरण है जहां इनपुट को सभी पॉसिबल इनपुट के विशेष उपसमूह से संबंधित होने का प्रॉमिस किया जाता है।<ref>{{cite web | url = http://complexityzoo.net/Complexity_Zoo_Glossary#P | title = वादा समस्या| website = [[Complexity Zoo]] }}</ref> डिसीजन प्रॉब्लम्स के विपरीत, यैस इंस्टैंस (वे इनपुट जिनके लिए एल्गोरिदम को यैस रिटर्न करना चाहिए) और | [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कॉम्पलेक्सिटी थ्योरी]] में, '''प्रॉमिस प्रॉब्लम''' [[निर्णय समस्या|डिसीजन प्रॉब्लम]] का सामान्यीकरण है जहां इनपुट को सभी पॉसिबल इनपुट के विशेष उपसमूह से संबंधित होने का प्रॉमिस किया जाता है।<ref>{{cite web | url = http://complexityzoo.net/Complexity_Zoo_Glossary#P | title = वादा समस्या| website = [[Complexity Zoo]] }}</ref> डिसीजन प्रॉब्लम्स के विपरीत, यैस इंस्टैंस (वे इनपुट जिनके लिए एल्गोरिदम को यैस रिटर्न करना चाहिए) और नो इंस्टैंस सभी इनपुट के समुच्चय को समाप्त नहीं करते हैं। इन्टुइटिवेली, एल्गोरिदम से प्रॉमिस किया गया है कि इनपुट सचमुच में यह यैस इन्सटेंसेस या नो इन्सटेंसेस के समुच्चय से संबंधित है। ऐसे इनपुट भी हो सकते हैं जो न तो यैस हों और न ही नो हों, यदि किसी प्रॉमिस की प्रॉब्लम का समाधान करने के लिए एल्गोरिदम को ऐसा इनपुट दिया जाता है, तो एल्गोरिदम को कुछ भी आउटपुट देने की अनुमति होती है, और यहां तक कि यह रुक भी नहीं सकता है। | ||
==औपचारिक परिभाषा== | ==औपचारिक परिभाषा== | ||
इसी प्रकार डिसीजन प्रॉब्लम [[औपचारिक भाषा]] <math>L \subseteq \{0,1\}^*</math> से जुड़ी हो सकती है, जहां प्रॉब्लम <math>L</math> में सभी इनपुट को | इसी प्रकार डिसीजन प्रॉब्लम [[औपचारिक भाषा]] <math>L \subseteq \{0,1\}^*</math> से जुड़ी हो सकती है, जहां प्रॉब्लम <math>L</math> में सभी इनपुट को एक्सेप्ट करना और इसके अतिरिक्त <math>L</math> में नहीं, अपितु सभी इनपुट को रिजैक्ट करना भी है। प्रॉमिस प्रॉब्लम के लिए, दो लैंग्वेज हैं, <math>L_{\text{YES}}</math> और <math>L_{\text{NO}}</math>, जो [[असंयुक्त सेट|डिसजोइन्ट]] होना चाहिए, जिसका अर्थ है <math>L_{\text{YES}} \cap L_{\text{NO}} = \varnothing</math>, जैसे कि <math>L_{\text{YES}}</math> में सभी इनपुट को एक्सेप्ट किया जाना चाहिए और <math>L_{\text{NO}}</math> में सभी इनपुट रिजैक्ट कर दिया जाना चाहिए, समुच्चय <math>L_{\text{YES}} \cup L_{\text{NO}}</math> को प्रॉमिस कहा जाता है। यदि इनपुट प्रॉमिस से संबंधित नहीं है तो आउटपुट पर इसकी कोई आवश्यकता नहीं होती है। यदि प्रॉमिस <math>\{0,1\}^*</math> के समतुल्य है, तो यह भी डिसीजन प्रॉब्लम है, और प्रॉमिस को ट्रिविअल कहा जाता है। | ||
==इंस्टैंस== | ==इंस्टैंस== | ||
इसी प्रकार कई नैचूरल प्रॉब्लम्स | इसी प्रकार कई नैचूरल प्रॉब्लम्स सचमुच में प्रॉमिस प्रॉब्लम्स हैं। इंस्टैंस के लिए, निम्नलिखित प्रॉब्लम पर विचार करें: [[निर्देशित अचक्रीय ग्राफ|डायरेक्टेड एसाइक्लिक ग्राफ]] को देखते हुए, निर्धारित करें कि क्या ग्राफ में लंबाई 10 का [[पथ (ग्राफ सिद्धांत)|पाथ (ग्राफ थ्योरी)]] है। यैस इन्सटेंसेस लंबाई 10 के पाथ के साथ डायरेक्टेड एसाइक्लिक ग्राफ हैं, जबकि कोई भी इंस्टैंस लंबाई 10 के पाथ के साथ डायरेक्टेड एसाइक्लिक ग्राफ नहीं है। प्रॉमिस डायरेक्टेड एसाइक्लिक ग्राफ का समुच्चय है। इस इंस्टैंस में, प्रॉमिस को चैक करना सरल है। विशेष रूप से, यह चैक करना बहुत सरल है कि दिया गया ग्राफ़ साइक्लिक है या नहीं चूंकि, प्रॉमिस की गई प्रॉपर्टी का मूल्यांकन करना कठिन हो सकता है। इंस्टैंस के लिए, [[हैमिल्टनियन ग्राफ]] को देखते हुए प्रॉब्लम पर विचार करें और इसके अतिरक्त यह निर्धारित भी करें कि क्या ग्राफ में 4 आकार का [[चक्र (ग्राफ सिद्धांत)|साईकल (ग्राफ थ्योरी)]] है। अब प्रॉमिस का मूल्यांकन करना एनपी-हार्ड है, फिर भी प्रॉमिस की प्रॉब्लम का समाधान करना सरल है क्योंकि आकार 4 के साईकल की जांच पॉलीनोमिअल टाइम में की जा सकती है। | ||
==यह भी देखें== | ==यह भी देखें== | ||
Revision as of 20:59, 8 August 2023
कम्प्यूटेशनल कॉम्पलेक्सिटी थ्योरी में, प्रॉमिस प्रॉब्लम डिसीजन प्रॉब्लम का सामान्यीकरण है जहां इनपुट को सभी पॉसिबल इनपुट के विशेष उपसमूह से संबंधित होने का प्रॉमिस किया जाता है।[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.
श्रेणी:कम्प्यूटेशनल प्रॉब्लम्स
