ब्लम अभिगृहीत: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| 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>\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> समुच्चयों की समष्टि वर्ग के रूप में सोचा जा सकता है। | ||
== संदर्भ == | == संदर्भ == | ||
Revision as of 23:55, 5 August 2023
कम्प्यूटेशनल कोम्प्लेक्सिटी सिद्धांत में ब्लम एक्सिओम्स या ब्लम कोम्प्लेक्सिटी एक्सिओम्स सिद्धांत हैं जो गणना योग्य कार्यों के समुच्चय पर समष्टि उपायों के वांछनीय गुणों को निर्दिष्ट करते हैं। एक्सिओम्स को सर्वप्रथम 1967 में मैनुअल ब्लम द्वारा परिभाषित किया गया था।[1]
महत्वपूर्ण रूप से, ब्लम की स्पीडअप प्रमेय और गैप प्रमेय इन सिद्धांतों को संतुष्ट करने वाले किसी भी समष्टि माप के लिए मान्य हैं। इन सिद्धांतों को संतुष्ट करने वाले सबसे प्रसिद्ध उपाय समय (अर्थात, चलने का समय) और समष्टि (अर्थात, मेमोरी उपयोग) हैं।
परिभाषाएँ
ब्लम समष्टि माप जोड़ी है साथ आंशिक संगणनीय फलन की संख्या गणना योग्य फलन हैं:
जो निम्नलिखित ब्लम सिद्धांतों को संतुष्ट करता है। हम लिखते हैं गोडेल नंबरिंग के अंतर्गत आई-वें आंशिक गणना योग्य फलन के लिए , और आंशिक गणना योग्य फलन के लिए हैं:
- किसी फलन का डोमेन और समरूप हैं।
- समुच्चय पुनरावर्ती हैं।
उदाहरण
- समष्टि माप है, यदि i द्वारा कोडित गणना के लिए या तो समय या मेमोरी (या उसका कुछ उपयुक्त संयोजन) आवश्यक है।
- यह समष्टि माप नहीं है, क्योंकि यह दूसरे सिद्धांत को विफल करता है।
समष्टि वर्ग
कुल गणना योग्य फलन के लिए गणना योग्य फलन की समष्टि वर्गों को इस प्रकार परिभाषित किया जा सकता है:
से कम समष्टि वाले सभी गणना योग्य फलन का समूह है, से कम समष्टि वाले सभी बूलियन-मूल्यवान फलन का समुच्चय है। यदि हम उन फलन को समुच्चय पर संकेतक फलन के रूप में मानते हैं, समुच्चयों की समष्टि वर्ग के रूप में सोचा जा सकता है।
संदर्भ
- ↑ Blum, Manuel (1967). "पुनरावर्ती कार्यों की जटिलता का एक मशीन-स्वतंत्र सिद्धांत" (PDF). Journal of the ACM. 14 (2): 322–336. doi:10.1145/321386.321395. S2CID 15710280.
