प्रॉमिस प्रॉब्लम: Difference between revisions

From Vigyanwiki
m (Abhishek moved page वादा समस्या to प्रॉमिस प्रॉब्लम without leaving a redirect)
No edit summary
 
(5 intermediate revisions by 3 users not shown)
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</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> के समतुल्य है, तो यह भी एक डिसीजन प्रॉब्लम है, और प्रॉमिस को ट्रिविअल कहा जाता है।
इसी प्रकार डिसीजन प्रॉब्लम [[औपचारिक भाषा]] <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 के साइकिल्स की जांच बहुपद समय में की जा सकती है।
इसी प्रकार कई नैचूरल प्रॉब्लम्स वास्तव में प्रॉमिस प्रॉब्लम्स हैं। इंस्टैंस के लिए, निम्नलिखित प्रॉब्लम पर विचार करें: [[निर्देशित अचक्रीय ग्राफ|डायरेक्टेड एसाइक्लिक ग्राफ]] को देखते हुए, निर्धारित करें कि क्या ग्राफ में लंबाई 10 का [[पथ (ग्राफ सिद्धांत)|पाथ (ग्राफ थ्योरी)]] है। यैस इन्सटेंसेस लंबाई 10 के पाथ के साथ डायरेक्टेड एसाइक्लिक ग्राफ हैं, जबकि कोई भी इंस्टैंस लंबाई 10 के पाथ के साथ डायरेक्टेड एसाइक्लिक ग्राफ नहीं है। प्रॉमिस डायरेक्टेड एसाइक्लिक ग्राफ का समुच्चय है। इस इंस्टैंस में, प्रॉमिस को चैक करना सरल है। विशेष रूप से, यह चैक करना बहुत सरल है कि दिया गया ग्राफ़ साइक्लिक है या नहीं चूंकि, प्रॉमिस की गई प्रॉपर्टी का मूल्यांकन करना कठिन हो सकता है। इंस्टैंस के लिए, [[हैमिल्टनियन ग्राफ]] को देखते हुए प्रॉब्लम पर विचार करें और इसके अतिरक्त यह निर्धारित भी करें कि क्या ग्राफ में 4 आकार का [[चक्र (ग्राफ सिद्धांत)|साईकल (ग्राफ थ्योरी)]] है। अब प्रॉमिस का मूल्यांकन करना एनपी-हार्ड है, फिर भी प्रॉमिस की प्रॉब्लम का समाधान करना सरल है क्योंकि आकार 4 के साईकल की जांच बहुपद समय में की जा सकती है।


==यह भी देखें==
==यह भी देखें==
Line 62: Line 62:
श्रेणी:कम्प्यूटेशनल प्रॉब्लम्स
श्रेणी:कम्प्यूटेशनल प्रॉब्लम्स


[[Category: Machine Translated Page]]
[[Category:Created On 25/07/2023]]
[[Category:Created On 25/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]

Latest revision as of 09:54, 23 August 2023

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

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

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

इंस्टैंस

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

यह भी देखें

संदर्भ

  1. "वादा समस्या". Complexity Zoo.



सर्वेक्षण

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