ब्लम अभिगृहीत: Difference between revisions
From Vigyanwiki
No edit summary |
m (8 revisions imported from alpha:ब्लम_अभिगृहीत) |
||
| (4 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कोम्प्लेक्सिटी | [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कोम्प्लेक्सिटी थ्योरी]] में '''ब्लम एक्सिओम्स''' या ब्लम कोम्प्लेक्सिटी एक्सिओम्स थ्योरी हैं जो [[गणना योग्य कार्य|कॉम्प्टेबल फंक्शन]] के सेट पर कम्पलेक्सिटी उपायों के डेसिरबल गुणों को स्पेसिफाई करते हैं। एक्सिओम्स को सर्वप्रथम 1967 में [[मैनुअल ब्लम]] द्वारा परिभाषित किया गया था।<ref>{{Cite journal | last = Blum | first = Manuel | authorlink = Manuel Blum| title = पुनरावर्ती कार्यों की जटिलता का एक मशीन-स्वतंत्र सिद्धांत| doi = 10.1145/321386.321395 | journal = [[Journal of the ACM]]| volume = 14 | issue = 2 | pages = 322–336| year = 1967 | s2cid = 15710280 | url = http://port70.net/~nsz/articles/classic/blum_complexity_1976.pdf}}</ref> | ||
महत्वपूर्ण रूप से, ब्लम की स्पीडअप प्रमेय और [[गैप प्रमेय]] इन सिद्धांतों को संतुष्ट करने वाले किसी भी | महत्वपूर्ण रूप से, ब्लम की स्पीडअप प्रमेय और [[गैप प्रमेय]] इन सिद्धांतों को संतुष्ट करने वाले किसी भी कम्पलेक्सिटी माप के लिए मान्य हैं। इन सिद्धांतों को संतुष्ट करने वाले सबसे प्रसिद्ध उपाय टाइम (अर्थात, चलने का समय) और स्पेस (अर्थात, मेमोरी उपयोग) हैं। | ||
== परिभाषाएँ == | == परिभाषाएँ == | ||
ब्लम | ब्लम कम्पलेक्सिटी माप जोड़ी <math>(\varphi, \Phi)</math> है साथ <math>\varphi</math> आंशिक संगणनीय फंक्शन की संख्या <math>\mathbf{P}^{(1)}</math>कम्प्युटेबल फंक्शन हैं: | ||
:<math>\Phi: \mathbb{N} \to \mathbf{P}^{(1)}</math> | :<math>\Phi: \mathbb{N} \to \mathbf{P}^{(1)}</math> | ||
जो निम्नलिखित ब्लम सिद्धांतों को संतुष्ट करता है। हम लिखते हैं <math>\varphi_i</math> गोडेल नंबरिंग के अंतर्गत आई-वें आंशिक | जो निम्नलिखित ब्लम सिद्धांतों को संतुष्ट करता है। हम लिखते हैं <math>\varphi_i</math> गोडेल नंबरिंग के अंतर्गत आई-वें आंशिक कम्प्युटेबल फंक्शन के लिए <math>\varphi</math>, और <math>\Phi_i</math> आंशिक कम्प्युटेबल फंक्शन के लिए <math>\Phi(i)</math> हैं: | ||
* [[किसी फ़ंक्शन का डोमेन|किसी | * [[किसी फ़ंक्शन का डोमेन|किसी फंक्शन का डोमेन]] <math>\varphi_i</math> और <math>\Phi_i</math> समरूप हैं। | ||
* | * सेट <math>\{(i,x,t) \in \mathbb{N}^3 | \Phi_i(x) = t\}</math> पुनरावर्ती हैं। | ||
=== उदाहरण === | === उदाहरण === | ||
* <math>(\varphi, \Phi)</math> | * <math>(\varphi, \Phi)</math> कम्पलेक्सिटी माप है, यदि <math>\Phi</math> i द्वारा कोडित गणना के लिए या तो समय या मेमोरी (या उसका कुछ उपयुक्त संयोजन) आवश्यक है। | ||
* <math>(\varphi, \varphi)</math> यह | * <math>(\varphi, \varphi)</math> यह कम्पलेक्सिटी माप नहीं है, क्योंकि यह दूसरे थ्योरी को विफल करता है। | ||
== | == कम्पलेक्सिटी वर्ग == | ||
कम्प्युटेबल फंक्शन <math>f</math> के लिए [[जटिलता वर्ग|कम्पलेक्सिटी वर्गों]] को इस प्रकार परिभाषित किया जा सकता है: | |||
:<math>C(f) := \{ \varphi_i \in \mathbf{P}^{(1)} | \forall x.\ \Phi_i(x) \leq f(x) \}</math> | :<math>C(f) := \{ \varphi_i \in \mathbf{P}^{(1)} | \forall x.\ \Phi_i(x) \leq f(x) \}</math> | ||
:<math>C^0(f) := \{ h \in C(f) | \mathrm{codom}(h) \subseteq \{0,1\} \}</math> | :<math>C^0(f) := \{ h \in C(f) | \mathrm{codom}(h) \subseteq \{0,1\} \}</math> | ||
<math>C(f)</math> से कम | <math>C(f)</math> से कम कम्पलेक्सिटी वाले सभी कम्प्युटेबल फंक्शन का समूह <math>f</math> है, <math>C^0(f)</math> से कम कम्पलेक्सिटी वाले सभी बूलियन-वैल्यूड फंक्शन का सेट <math>f</math> है। यदि हम उन फंक्शन को सेट पर संकेतक फंक्शन के रूप में मानते हैं, <math>C^0(f)</math> सेट की कम्पलेक्सिटी वर्ग के रूप में सोचा जा सकता है। | ||
== संदर्भ == | == संदर्भ == | ||
| Line 33: | Line 33: | ||
[[Category: Machine Translated Page]] | [[Category: Machine Translated Page]] | ||
[[Category:Created On 25/07/2023]] | [[Category:Created On 25/07/2023]] | ||
[[Category:Vigyan Ready]] | |||
Latest revision as of 22:28, 2 February 2024
कम्प्यूटेशनल कोम्प्लेक्सिटी थ्योरी में ब्लम एक्सिओम्स या ब्लम कोम्प्लेक्सिटी एक्सिओम्स थ्योरी हैं जो कॉम्प्टेबल फंक्शन के सेट पर कम्पलेक्सिटी उपायों के डेसिरबल गुणों को स्पेसिफाई करते हैं। एक्सिओम्स को सर्वप्रथम 1967 में मैनुअल ब्लम द्वारा परिभाषित किया गया था।[1]
महत्वपूर्ण रूप से, ब्लम की स्पीडअप प्रमेय और गैप प्रमेय इन सिद्धांतों को संतुष्ट करने वाले किसी भी कम्पलेक्सिटी माप के लिए मान्य हैं। इन सिद्धांतों को संतुष्ट करने वाले सबसे प्रसिद्ध उपाय टाइम (अर्थात, चलने का समय) और स्पेस (अर्थात, मेमोरी उपयोग) हैं।
परिभाषाएँ
ब्लम कम्पलेक्सिटी माप जोड़ी है साथ आंशिक संगणनीय फंक्शन की संख्या कम्प्युटेबल फंक्शन हैं:
जो निम्नलिखित ब्लम सिद्धांतों को संतुष्ट करता है। हम लिखते हैं गोडेल नंबरिंग के अंतर्गत आई-वें आंशिक कम्प्युटेबल फंक्शन के लिए , और आंशिक कम्प्युटेबल फंक्शन के लिए हैं:
- किसी फंक्शन का डोमेन और समरूप हैं।
- सेट पुनरावर्ती हैं।
उदाहरण
- कम्पलेक्सिटी माप है, यदि i द्वारा कोडित गणना के लिए या तो समय या मेमोरी (या उसका कुछ उपयुक्त संयोजन) आवश्यक है।
- यह कम्पलेक्सिटी माप नहीं है, क्योंकि यह दूसरे थ्योरी को विफल करता है।
कम्पलेक्सिटी वर्ग
कम्प्युटेबल फंक्शन के लिए कम्पलेक्सिटी वर्गों को इस प्रकार परिभाषित किया जा सकता है:
से कम कम्पलेक्सिटी वाले सभी कम्प्युटेबल फंक्शन का समूह है, से कम कम्पलेक्सिटी वाले सभी बूलियन-वैल्यूड फंक्शन का सेट है। यदि हम उन फंक्शन को सेट पर संकेतक फंक्शन के रूप में मानते हैं, सेट की कम्पलेक्सिटी वर्ग के रूप में सोचा जा सकता है।
संदर्भ
- ↑ Blum, Manuel (1967). "पुनरावर्ती कार्यों की जटिलता का एक मशीन-स्वतंत्र सिद्धांत" (PDF). Journal of the ACM. 14 (2): 322–336. doi:10.1145/321386.321395. S2CID 15710280.
