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

Latest revision as of 09:54, 23 August 2023

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

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

इसी प्रकार डिसीजन प्रॉब्लम औपचारिक भाषा $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 के साईकल की जांच बहुपद समय में की जा सकती है।

यह भी देखें

संदर्भ

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

सर्वेक्षण

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.

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

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

[1]

@@ Line 1: / Line 1: @@
 {{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 60: / Line 60: @@
 }}
-श्रेणी:कम्प्यूटेशनल समस्याएँ
+श्रेणी:कम्प्यूटेशनल प्रॉब्लम्स
-[[Category: Machine Translated Page]]
 [[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]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 09:54, 23 August 2023

Contents

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

इंस्टैंस

यह भी देखें

संदर्भ

सर्वेक्षण

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 09:54, 23 August 2023

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

इंस्टैंस

यह भी देखें

संदर्भ

सर्वेक्षण

Navigation

Wiki tools

Page tools

Other projects

Hidden categories