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

कम्प्यूटेशनल कोम्प्लेक्सिटी सिद्धांत में ब्लम एक्सिओम्स या ब्लम कोम्प्लेक्सिटी एक्सिओम्स सिद्धांत हैं जो गणना योग्य फलनों के समुच्चय पर समष्टि उपायों के वांछनीय गुणों को निर्दिष्ट करते हैं। एक्सिओम्स को सर्वप्रथम 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)$ समुच्चयों की समष्टि वर्ग के रूप में सोचा जा सकता है।