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

Latest revision as of 11:53, 2 February 2024

कम्प्यूटेशनल कोम्प्लेक्सिटी थ्योरी में ब्लम एक्सिओम्स या ब्लम कोम्प्लेक्सिटी एक्सिओम्स थ्योरी हैं जो कॉम्प्टेबल फंक्शन के सेट पर कम्पलेक्सिटी उपायों के डेसिरबल गुणों को स्पेसिफाई करते हैं। एक्सिओम्स को सर्वप्रथम 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> आंशिक संगणनीय कार्यों का क्रमांकन_(computability_theory)। <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> सेट की कम्पलेक्सिटी वर्ग के रूप में सोचा जा सकता है।
 == संदर्भ ==
@@ Line 32: / Line 33: @@
 [[Category: Machine Translated Page]]
 [[Category:Created On 25/07/2023]]
+[[Category:Vigyan Ready]]

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

Latest revision as of 11:53, 2 February 2024

Contents

परिभाषाएँ

उदाहरण

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

संदर्भ

Navigation menu

Search