ब्लम अभिगृहीत

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

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

परिभाषाएँ

ब्लम कम्पलेक्सिटी माप जोड़ी $(\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)$ सेट की कम्पलेक्सिटी वर्ग के रूप में सोचा जा सकता है।