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

Revision as of 20:52, 7 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]]

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 20:52, 7 August 2023

Contents

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

उदाहरण

यह भी देखें

संदर्भ

सर्वेक्षण

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 20:52, 7 August 2023

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

उदाहरण

यह भी देखें

संदर्भ

सर्वेक्षण

Navigation

Wiki tools

Page tools

Other projects

Hidden categories