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

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

परिभाषाएँ

ब्लम जटिलता माप एक जोड़ी है $(\varphi ,\Phi )$ साथ $\varphi$ आंशिक संगणनीय कार्यों का क्रमांकन_(computability_theory)। $\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)$ सेटों की जटिलता वर्ग के रूप में सोचा जा सकता है।