ब्लम अभिगृहीत: Difference between revisions

Revision as of 19:38, 7 September 2023

कम्प्यूटेशनल कोम्प्लेक्सिटी सिद्धांत में ब्लम एक्सिओम्स या ब्लम कोम्प्लेक्सिटी एक्सिओम्स सिद्धांत हैं जो कॉम्प्टेबल फंक्शन के सेट पर कम्पलेक्सिटी उपायों के वांछनीय गुणों को स्पेसिफाई करते हैं। एक्सिओम्स को सर्वप्रथम 1967 में मैनुअल ब्लम द्वारा परिभाषित किया गया था।^[1]

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

परिभाषाएँ

ब्लम कम्पलेक्सिटी माप जोड़ी $(\varphi ,\Phi )$ है साथ $\varphi$ आंशिक संगणनीय फंक्शन की संख्या $\mathbf {P} ^{(1)}$ कम्प्युटेबल फंक्शन हैं:

\Phi :\mathbb {N} \to \mathbf {P} ^{(1)}

जो निम्नलिखित ब्लम सिद्धांतों को संतुष्ट करता है। हम लिखते हैं $\varphi _{i}$ गोडेल नंबरिंग के अंतर्गत आई-वें आंशिक कम्प्युटेबल फंक्शन के लिए $\varphi$ , और $\Phi _{i}$ आंशिक कम्प्युटेबल फंक्शन के लिए $\Phi (i)$ हैं:

किसी फंक्शन का डोमेन $\varphi _{i}$ और $\Phi _{i}$ समरूप हैं।
सेट $\{(i,x,t)\in \mathbb {N} ^{3}|\Phi _{i}(x)=t\}$ पुनरावर्ती हैं।

उदाहरण

$(\varphi ,\Phi )$ कम्पलेक्सिटी माप है, यदि $\Phi$ i द्वारा कोडित गणना के लिए या तो समय या मेमोरी (या उसका कुछ उपयुक्त संयोजन) आवश्यक है।
$(\varphi ,\varphi )$ यह कम्पलेक्सिटी माप नहीं है, क्योंकि यह दूसरे सिद्धांत को विफल करता है।

कम्पलेक्सिटी वर्ग

कम्प्युटेबल फंक्शन $f$ के लिए कम्पलेक्सिटी वर्गों को इस प्रकार परिभाषित किया जा सकता है:

C(f):=\{\varphi _{i}\in \mathbf {P} ^{(1)}|\forall x.\ \Phi _{i}(x)\leq f(x)\}

C^{0}(f):=\{h\in C(f)|\mathrm {codom} (h)\subseteq \{0,1\}\}

$C(f)$ से कम कम्पलेक्सिटी वाले सभी कम्प्युटेबल फंक्शन का समूह $f$ है, $C^{0}(f)$ से कम कम्पलेक्सिटी वाले सभी बूलियन-वैल्यूड फंक्शन का सेट $f$ है। यदि हम उन फंक्शन को सेट पर संकेतक फंक्शन के रूप में मानते हैं, $C^{0}(f)$ सेट की कम्पलेक्सिटी वर्ग के रूप में सोचा जा सकता है।

संदर्भ

↑ Blum, Manuel (1967). "पुनरावर्ती कार्यों की जटिलता का एक मशीन-स्वतंत्र सिद्धांत" (PDF). Journal of the ACM. 14 (2): 322–336. doi:10.1145/321386.321395. S2CID 15710280.

[1] Blum, Manuel (1967). "पुनरावर्ती कार्यों की जटिलता का एक मशीन-स्वतंत्र सिद्धांत" (PDF). Journal of the ACM. 14 (2): 322–336. doi:10.1145/321386.321395. S2CID 15710280.

[1]

@@ 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>
+[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कोम्प्लेक्सिटी सिद्धांत]] में '''ब्लम एक्सिओम्स''' या ब्लम कोम्प्लेक्सिटी एक्सिओम्स सिद्धांत हैं जो [[गणना योग्य कार्य|कॉम्प्टेबल फंक्शन]] के सेट पर कम्पलेक्सिटी उपायों के वांछनीय गुणों को स्पेसिफाई करते हैं। एक्सिओम्स को सर्वप्रथम 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>(\varphi, \Phi)</math> है साथ <math>\varphi</math> आंशिक संगणनीय फंक्शन की संख्या <math>\mathbf{P}^{(1)}</math>कम्प्युटेबल फंक्शन हैं:
 :<math>\Phi: \mathbb{N} \to \mathbf{P}^{(1)}</math>
-जो निम्नलिखित ब्लम सिद्धांतों को संतुष्ट करता है। हम लिखते हैं <math>\varphi_i</math> गोडेल नंबरिंग के अंतर्गत आई-वें आंशिक गणना योग्य फलन के लिए <math>\varphi</math>, और <math>\Phi_i</math> आंशिक गणना योग्य फलन के लिए <math>\Phi(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>\{(i,x,t) \in \mathbb{N}^3 | \Phi_i(x) = t\}</math> पुनरावर्ती हैं।
 === उदाहरण ===
-*  <math>(\varphi, \Phi)</math> समष्टि माप है, यदि <math>\Phi</math> i द्वारा कोडित गणना के लिए या तो समय या मेमोरी (या उसका कुछ उपयुक्त संयोजन) आवश्यक है।
+*  <math>(\varphi, \Phi)</math> कम्पलेक्सिटी माप है, यदि <math>\Phi</math> i द्वारा कोडित गणना के लिए या तो समय या मेमोरी (या उसका कुछ उपयुक्त संयोजन) आवश्यक है।
-*  <math>(\varphi, \varphi)</math> यह समष्टि माप नहीं है, क्योंकि यह दूसरे सिद्धांत को विफल करता है।
+*  <math>(\varphi, \varphi)</math> यह कम्पलेक्सिटी माप नहीं है, क्योंकि यह दूसरे सिद्धांत को विफल करता है।
-== समष्टि वर्ग ==
+== कम्पलेक्सिटी वर्ग ==
-कुल गणना योग्य फलन के लिए <math>f</math> गणना योग्य फलन की [[जटिलता वर्ग|समष्टि वर्गों]] को इस प्रकार परिभाषित किया जा सकता है:
+कम्प्युटेबल फंक्शन <math>f</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(f)</math> से कम समष्टि वाले सभी गणना योग्य फलन का समूह <math>f</math> है, <math>C^0(f)</math> से कम समष्टि वाले सभी बूलियन-मूल्यवान फलन का समुच्चय <math>f</math> है। यदि हम उन फलन को समुच्चय पर संकेतक फलन के रूप में मानते हैं, <math>C^0(f)</math> समुच्चयों की समष्टि वर्ग के रूप में सोचा जा सकता है।
+<math>C(f)</math> से कम कम्पलेक्सिटी वाले सभी कम्प्युटेबल फंक्शन का समूह <math>f</math> है, <math>C^0(f)</math> से कम कम्पलेक्सिटी वाले सभी बूलियन-वैल्यूड फंक्शन का सेट <math>f</math> है। यदि हम उन फंक्शन को सेट पर संकेतक फंक्शन के रूप में मानते हैं, <math>C^0(f)</math> सेट की कम्पलेक्सिटी वर्ग के रूप में सोचा जा सकता है।
 == संदर्भ ==

Anonymous

Search

ब्लम अभिगृहीत: Difference between revisions

Namespaces

More

Page actions

Revision as of 19:38, 7 September 2023

Contents

परिभाषाएँ

उदाहरण

कम्पलेक्सिटी वर्ग

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

ब्लम अभिगृहीत: Difference between revisions

Revision as of 19:38, 7 September 2023

परिभाषाएँ

उदाहरण

कम्पलेक्सिटी वर्ग

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories