डिसीजन ट्री मॉडल

अभिकलनात्मक सम्मिश्रता में निर्णय वृक्ष मॉडल गणना का मॉडल है जिसमें एक एल्गोरिथ्म को मूल रूप से एक निर्णय वृक्ष माना जाता है, अर्थात, प्रश्नों या परीक्षणों का एक क्रम जो अनुकूली विधि से किया जाता है, इसलिए पिछले परीक्षणों के परिणाम अगले किए गए परीक्षणों को प्रभावित कर सकते हैं।

सामान्यतः, इन परीक्षणों में परिणामों की एक छोटी संख्या होती है (जैसे हां-नहीं प्रश्न) और इन्हें जल्दी से निष्पादित किया जा सकता है (जैसे, इकाई अभिकलनात्मक लागत के साथ), इसलिए निर्णय वृक्ष मॉडल में एल्गोरिदम की सबसे खराब स्थिति समय सम्मिश्रता से मेल खाती है संबंधित निर्णय वृक्ष की गहराई निर्णय वृक्ष मॉडल में किसी समस्या या एल्गोरिदम की अभिकलनात्मक सम्मिश्रता की इस धारणा को इसकी निर्णय वृक्ष सम्मिश्रता या क्वेरी सम्मिश्रता कहा जाता है।

निर्णय वृक्ष मॉडल अभिकलनात्मक समस्याओं और एल्गोरिदम के कुछ वर्गों के लिए सम्मिश्रता सिद्धांत के लिए निम्न परिबद्ध स्थापित करने में सहायक होते हैं। अभिकलनात्मक मॉडल और क्वेरी एल्गोरिदम के प्रकार के आधार पर निर्णय वृक्ष मॉडल के कई प्रकार प्रस्तुत किए गए हैं।

उदाहरण के लिए, एक निर्णय वृक्ष तर्क का उपयोग यह दिखाने के लिए किया जाता है, कि तुलनात्मक प्रकार $n$ आइटम अवश्य लेने होता है, $n\log(n)$ तुलना की जाती है। तुलना प्रकारों के लिए, एक क्वेरी दो वस्तुओं की तुलना है, ए, बी दो परिणामों के साथ (यह मानते हुए कि कोई आइटम समान नहीं हैं), या तो ए<बी या ए>बी, इस मॉडल में तुलना प्रकारों को निर्णय वृक्ष के रूप में व्यक्त किया जा सकता है, क्योंकि ऐसे सॉर्टिंग एल्गोरिदम मात्र इस प्रकार के प्रश्नों को निष्पादित करते हैं।

छंटाई के लिए वृक्ष और निम्न परिबद्धओं की तुलना करें

सॉर्टिंग और अन्य समान समस्याओं के लिए एल्गोरिदम को समझने के लिए अधिकांशतः निर्णय वृक्षों का उपयोग किया जाता है, यह सबसे पहले फोर्ड और जॉनसन द्वारा किया गया है।

उदाहरण के लिए, कई सॉर्टिंग एल्गोरिदम तुलनात्मक सॉर्ट हैं, जिसका अर्थ है, कि वे मात्र इनपुट अनुक्रम के बारे में जानकारी प्राप्त करते हैं, $x_{1},x_{2},\ldots ,x_{n}$ स्थानीय तुलनाओं के माध्यम से: परीक्षण करना कि क्या $x_{i}<x_{j}$, $x_{i}=x_{j}$, या $x_{i}>x_{j}$, यह मानते हुए कि क्रमबद्ध की जाने वाली सभी वस्तुएँ विशिष्ट और तुलनीय हैं, $x_{i}>x_{j}$है? इसे हाँ-या-नहीं प्रश्न के रूप में दोहराया जा सकता है।

इन एल्गोरिदम को बाइनरी निर्णय वृक्ष के रूप में तैयार किया जा सकता है, जहां प्रश्न तुलना हैं, एक आंतरिक नोड एक प्रश्न से मेल खाता है, और नोड के बच्चे अगली क्वेरी के अनुरूप होते हैं, जब प्रश्न का उत्तर हां या नहीं होता है। लीफ नोड्स के लिए, आउटपुट क्रमपरिवर्तन से मेल खाता है, $\pi$ जो बताता है, कि आइटमों की पूरी प्रकार से ऑर्डर की गई सूची से इनपुट अनुक्रम को कैसे खंगाला जाता है। (इस क्रमपरिवर्तन का उलटा, $\pi ^{-1}$, इनपुट अनुक्रम को पुनः व्यवस्थित करता है।)

कोई यह दिखा सकता है कि तुलना प्रकारों का उपयोग अवश्य करना होता है, $\Omega (n\log(n))$ एक सरल तर्क के माध्यम से तुलना एक एल्गोरिदम के सही होने के लिए, इसे हर संभव क्रमपरिवर्तन को आउटपुट करने में सक्षम होना चाहिए $n$ तत्व; अन्यथा, एल्गोरिदम इनपुट के रूप में उस विशेष क्रमपरिवर्तन के लिए विफल हो जाता है। इसलिए, इसके संगत निर्णय वृक्ष में कम से कम उतने ही पत्ते होने होते हैं, जितने क्रमपरिवर्तन हैं: $n!$ पत्तियाँ। कम से कम कोई बाइनरी ट्री $n!$ पत्तियों में कम से कम गहराई तो होती है, $\log _{2}(n!)=\Omega (n\log _{2}(n))$, इसलिए यह तुलनात्मक सॉर्टिंग एल्गोरिदम के रन टाइम पर निम्न परिबद्ध है। इस स्थिति में, इस समय की सम्मिश्रता वाले कई तुलना-सॉर्टिंग एल्गोरिदम का अस्तित्व, जैसे मर्जसॉर्ट और हीपसॉर्ट, दर्शाता है कि परिबद्ध तंग है।

यह तर्क क्वेरी के प्रकार के बारे में कुछ भी उपयोग नहीं करता है, इसलिए यह वास्तव में किसी भी सॉर्टिंग एल्गोरिदम के लिए निम्न परिबद्ध सिद्ध करता है, जिसे बाइनरी निर्णय पेड़ के रूप में मॉडल किया जा सकता है। संक्षेप में, यह सूचना-सैद्धांतिक तर्क का पुनर्लेखन है, कि एक सही सॉर्टिंग एल्गोरिदम को कम से कम सीखना होता है। $\log _{2}(n!)$ इनपुट अनुक्रम के बारे में जानकारी के अंश है, परिणामस्वरूप, यह यादृच्छिक निर्णय वृक्षों के लिए भी काम करता है।

अन्य निर्णय वृक्ष निम्न परिबद्ध का उपयोग यह करता है, कि क्वेरी एक तुलना है। उदाहरण के लिए, सबसे छोटी संख्या ज्ञात करने के लिए मात्र तुलनाओं का उपयोग करने के कार्य पर विचार करें $n$ एन नंबर है, जो सबसे छोटी संख्या निर्धारित करने से पहले, सबसे छोटी संख्या को छोड़कर प्रत्येक संख्या को कम से कम एक तुलना में "हारना" (बड़ी तुलना करना) होता है। तो, इसमें कम से कम समय लगता है, न्यूनतम ज्ञात करने के लिए n-1 तुलना होती है। यहां सूचना-सैद्धांतिक तर्क मात्र निम्न परिबद्ध देता है, एक समान तर्क ऑर्डर आँकड़ों की गणना के लिए सामान्य निम्न परिबद्ध के लिए काम करता है।

रैखिक और बीजगणितीय निर्णय वृक्ष

रैखिक निर्णय वृक्ष उपरोक्त तुलनात्मक निर्णय वृक्षों को वास्तविक वैक्टर लेने वाले अभिकलन कार्यों के लिए सामान्यीकृत करते हैं, $x\in \mathbb {R} ^{n}$ इनपुट के रूप में, रैखिक निर्णय वृक्षों में परीक्षण रैखिक कार्य हैं, वास्तविक संख्याओं की एक विशेष पसंद के लिए $a_{0},\dots ,a_{n}$, का $a_{0}+\textstyle \sum _{i=1}^{n}a_{i}x_{i}$चिह्न आउटपुट करें, (इस मॉडल में एल्गोरिदम मात्र आउटपुट के संकेत पर निर्भर हो सकते हैं।) तुलना वृक्ष रैखिक निर्णय वृक्ष हैं, $x_{i}-x_{j}$क्योंकि बीच की तुलना $x_{i}$ और $x_{j}$ रैखिक फ़ंक्शन से मेल खाता है, इसकी परिभाषा से, रैखिक निर्णय वृक्ष मात्र कार्य निर्दिष्ट कर सकते हैं, $f$ जिसके फ़ाइबर का निर्माण आधे-स्थानों के संघों और प्रतिच्छेदनों को लेकर किया जा सकता है।

बीजगणितीय निर्णय वृक्ष रैखिक निर्णय वृक्षों का एक सामान्यीकरण है, जो परीक्षण कार्यों को डिग्री के बहुपद होने की अनुमति देते हैं। $d$ ज्यामितीय रूप से, समष्टि को अर्ध-बीजगणितीय समूह (हाइपरसमतल का एक सामान्यीकरण) में विभाजित किया गया है।

राबिन और रींगोल्ड द्वारा परिभाषित ये निर्णय वृक्ष मॉडल, अधिकांशतः अभिकलनात्मक ज्यामिति में निम्न परिबद्ध सिद्ध करने के लिए उपयोग किए जाते हैं। उदाहरण के लिए, बेन-ऑर ने उस तत्व की विशिष्टता (अभिकलन का कार्य) दिखाई $f:\mathbb {R} ^{n}\to \{0,1\}$, कहां $f(x)$ 0 है, यदि और मात्र तभी जब भिन्न-भिन्न निर्देशांक उपलब्ध हों $i,j$ ऐसा है, $\Omega (n\log(n))$ कि $x_{i}=x_{j}$ को गहराई के बीजगणितीय निर्णय वृक्ष की आवश्यकता होती है, इसे पहली बार डोबकिन और लिप्टन द्वारा रैखिक निर्णय मॉडल के लिए दिखाया जाता है। वे यह भी दिखाते हैं, $n^{2}$ नैपसैक समस्या पर रैखिक निर्णय वृक्षों के लिए निम्न परिबद्ध, स्टील और याओ द्वारा बीजगणितीय निर्णय वृक्षों के लिए सामान्यीकृत होता है।

बूलियन निर्णय वृक्ष सम्मिश्रता

बूलियन निर्णय वृक्षों के लिए, कार्य एन-बिट बूलियन फ़ंक्शन के मान की गणना करना है, $f:\{0,1\}^{n}\to \{0,1\}$एक इनपुट के लिए $x\in \{0,1\}^{n}$, क्वेरीज़ इनपुट का थोड़ा सा पढ़ने से मेल खाती हैं, $x_{i}$, और $f(x)$ आउटपुट है, प्रत्येक क्वेरी पिछली क्वेरी पर निर्भर हो सकती है। निर्णय वृक्ष का उपयोग करने वाले कई प्रकार के अभिकलनात्मक मॉडल हैं, जिन पर विचार किया जा सकता है, कई सम्मिश्रता धारणाओं को स्वीकार करते हुए, सम्मिश्रता उपाय कहा जाता है।

नियतात्मक निर्णय वृक्ष

यदि निर्णय वृक्ष का आउटपुट है, $f(x)$ सभी के लिए $x\in \{0,1\}^{n}$, निर्णय वृक्ष $f$ को "गणना" करने के लिए कहा जाता है, किसी वृक्ष की गहराई, किसी पत्ते तक पहुंचने और परिणाम प्राप्त होने से पहले होने वाली प्रश्नों की अधिकतम संख्या है। $D(f)$, नियतात्मक निर्णय वृक्ष सम्मिश्रता $f$ गणना करने वाले सभी नियतात्मक निर्णय वृक्षों $f$ में सबसे छोटी गहराई है।

यादृच्छिक निर्णय वृक्ष

यादृच्छिक निर्णय वृक्ष को परिभाषित करने का एक विधि वृक्ष में अतिरिक्त नोड्स जोड़ना है, $p_{i}$प्रत्येक को एक संभावना द्वारा नियंत्रित किया जाता है, एक अन्य समकक्ष परिभाषा इसे नियतात्मक निर्णय वृक्षों पर वितरण के रूप में परिभाषित करना है। इस दूसरी परिभाषा के आधार पर, यादृच्छिक वृक्ष की सम्मिश्रता को अंतर्निहित वितरण के समर्थन में सभी वृक्ष के बीच सबसे बड़ी गहराई के रूप में परिभाषित किया गया है।

$R_{2}(f)$ को सबसे कम गहराई वाले यादृच्छिक निर्णय वृक्ष की सम्मिश्रता के रूप में परिभाषित किया गया है, जिसका परिणाम है, $f(x)$ कम से कम संभावना के साथ $2/3$ सभी के लिए � $x\in \{0,1\}^{n}$ (अर्थात्, परिबद्ध 2-तरफा त्रुटि के साथ) होता है। $R_{2}(f)$मोंटे कार्लो यादृच्छिक निर्णय-वृक्ष सम्मिश्रता के रूप में जाना जाता है, क्योंकि परिणाम को दो-तरफा त्रुटि के साथ गलत होने की अनुमति है। लास वेगास निर्णय-वृक्ष सम्मिश्रता $R_{0}(f)$ निर्णय वृक्ष की अपेक्षित गहराई को मापता है, जो सही होना चाहिए (अर्थात, शून्य-त्रुटि है)। एक तरफा बाउंडेड-एरर संस्करण भी है, $R_{1}(f)$जिसे द्वारा दर्शाया गया है।

नॉनडेटेमिनिस्टिक निर्णय वृक्ष

किसी फ़ंक्शन की गैर-नियतात्मक निर्णय वृक्ष सम्मिश्रता को सामान्यतः उस फ़ंक्शन की प्रमाणपत्र सम्मिश्रता के रूप में जाना जाता है। यह इनपुट बिट्स की संख्या को मापता है, जिसे एक गैर-नियतात्मक एल्गोरिदम को निश्चितता के साथ फ़ंक्शन का मूल्यांकन करने के लिए देखने की आवश्यकता होती है।

औपचारिक रूप से, प्रमाणपत्र सम्मिश्रता $f$ पर $x$ सूचकांकों के सबसे छोटे उपसमुच्चय का बनावट है, $S\subset [n]$ ऐसा कि, सभी के लिए $y\in \{0,1\}^{n}$, यदि $y_{i}=x_{i}$ सभी के लिए $i\in S$, तब $f(y)=f(x)$ है, की प्रमाणपत्र सम्मिश्रता $f$ सभी की तुलना में $x$ अधिकतम प्रमाणपत्र सम्मिश्रता है, अनुरूप धारणा जहां किसी को मात्र 2/3 संभावना के साथ सत्यापनकर्ता के सही होने की आवश्यकता होती है, $RC(f)$ उसे दर्शाया गया है।

क्वांटम निर्णय वृक्ष

क्वांटम निर्णय वृक्ष सम्मिश्रता $Q_{2}(f)$ सबसे कम गहराई वाले क्वांटम निर्णय वृक्ष की गहराई है, जो परिणाम होता है, $f(x)$ कम से कम संभावना के साथ 2 / 3 सभी के लिए $x\in \{0,1\}^{n}$, अन्य मात्रा, $Q_{E}(f)$, को परिणाम देने वाले सबसे कम गहराई वाले क्वांटम निर्णय वृक्ष की गहराई के रूप में परिभाषित किया गया है, $f(x)$ सभी स्थितियों में प्रायिकता 1 के साथ (अर्थात गणना करता है � एफ पूर्णतया)। $Q_{2}(f)$ और $Q_{E}(f)$ को सामान्यतः क्वांटम क्वेरी सम्मिश्रताओं के रूप में जाना जाता है, क्योंकि क्वांटम निर्णय वृक्ष की प्रत्यक्ष परिभाषा आधारित स्थिति की तुलना में अधिक जटिल है। यादृच्छिक स्थिति के समान, हम परिभाषित करते हैं।

ये धारणाएँ सामान्यतः डिग्री और अनुमानित डिग्री की धारणाओं से बंधी होती हैं। की डिग्री $f$, निरूपित $\deg(f)$, किसी भी बहुपद की सबसे छोटी डिग्री है, $p$ संतोषजनक $f(x)=p(x)$ सभी के लिए $x\in \{0,1\}^{n}$, की अनुमानित डिग्री $f$, निरूपित ${\widetilde {\deg }}(f)$, किसी भी बहुपद की सबसे छोटी डिग्री है, $p$ संतोषजनक $p(x)\in [0,1/3]$ जब भी $f(x)=0$ और $p(x)\in [2/3,1]$ जब भी $f(x)=1$.

बील्स एट अल. $Q_{0}(f)\geq \deg(f)/2$ और $Q_{2}(f)\geq {\widetilde {\deg }}(f)/2$ उसे स्थापित किया गया है.

बूलियन फ़ंक्शन सम्मिश्रता माध्यमों के बीच संबंध

यह परिभाषाओं से तुरंत पता चलता है कि $f$,$Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$, और $Q_{2}(f)\leq Q_{0}(f)\leq D(f)\leq n$ सभी के लिए $n$-बिट बूलियन फ़ंक्शन है, विपरीत दिशा में सर्वोत्तम ऊपरी सीमा ढूँढना क्वेरी सम्मिश्रता के क्षेत्र में एक प्रमुख लक्ष्य है।

इन सभी प्रकार की क्वेरी सम्मिश्रताएँ बहुपद से संबंधित हैं। ब्लम और इम्पाग्लियाज़ो, हार्टमैनिस और हेमचंद्र, और टार्डोस ने स्वतंत्र रूप से इसकी खोज की $D(f)\leq R_{0}(f)^{2}$, नोम निसान ने पाया कि$D(f)=O(R_{2}(f)^{3})$ मोंटे कार्लो यादृच्छिक निर्णय वृक्ष सम्मिश्रता भी बहुपद रूप से नियतात्मक निर्णय वृक्ष सम्मिश्रता से संबंधित है: (निसान ने यह भी दिखाया $D(f)=O(R_{1}(f)^{2})$) मोंटे कार्लो और $R_{0}(f)=O(R_{2}(f)^{2}\log R_{2}(f))$ लास वेगास मॉडल के बीच एक मजबूत संबंध ज्ञात है, यह संबंध बहुगणितीय कारकों तक इष्टतम है। क्वांटम निर्णय वृक्ष सम्मिश्रताओं के लिए, $D(f)=O(Q_{2}(f)^{4})$और यह परिबद्ध कड़ी है। $D(f)=O(Q_{0}(f)^{3})$ मिड्रिजनिस ने वह दिखाया है। बील्स एट अल के कारण चतुर्थक सीमा में सुधार होता है।

यह ध्यान रखना महत्वपूर्ण है, कि ये बहुपद संबंध मात्र कुल बूलियन कार्यों के लिए मान्य हैं। आंशिक बूलियन फ़ंक्शंस के लिए, $\{0,1\}^{n}$ जिसमें एक डोमेन का सबसमूह होता है, कि बीच एक घातांकीय पृथक्करण $Q_{0}(f)$ और $D(f)$ संभव है; ऐसी समस्या का पहला उदाहरण Deutsch और Jozsa द्वारा खोजा गया था।

संवेदनशीलता अनुमान

बूलियन फ़ंक्शन के लिए $f:\{0,1\}^{n}\to \{0,1\}$, की संवेदनशीलता $f$ को अधिकतम संवेदनशीलता के रूप में परिभाषित किया गया है, $f$ सब से ऊपर $x$, जहां की संवेदनशीलता $f$ पर $x$ एकल-बिट परिवर्तित की संख्या है, $x$ जो $f(x)$ का मान बदलता है, संवेदनशीलता बूलियन फ़ंक्शंस के विश्लेषण से कुल प्रभाव की धारणा से संबंधित है, $x$ जो सभी पर औसत संवेदनशीलता के समतुल्य है।

संवेदनशीलता अनुमान वह अनुमान है, कि संवेदनशीलता बहुपद रूप से क्वेरी सम्मिश्रता से संबंधित है, अर्थात् घातांक विद्यमान है, $c,c'$ ऐसा कि, सभी के लिए $f$, $D(f)=O(s(f)^{c})$ और $s(f)=O(D(f)^{c'})$है, $s(f)\leq D(f)$ कोई एक साधारण तर्क के माध्यम से यह दिखा सकता है, इसलिए अनुमान विशेष रूप से संवेदनशीलता के लिए निम्न सीमा खोजने के बारे में चिंतित है। चूंकि पहले चर्चा की गई सभी सम्मिश्रता माप बहुपद से संबंधित हैं, इसलिए उपयुक्त प्रकार की सम्मिश्रता माप प्रासंगिक नहीं है। चूंकि, इसे सामान्यतः ब्लॉक संवेदनशीलता के साथ संवेदनशीलता से संबंधित प्रश्न के रूप में व्यक्त किया जाता है।

की ब्लॉक संवेदनशीलता $f$, निरूपित $bs(f)$, की अधिकतम ब्लॉक संवेदनशीलता के रूप में परिभाषित किया गया है, $f$ सब से ऊपर $x$ की ब्लॉक संवेदनशीलता $f$ पर $x$ अधिकतम संख्या है, $t$ असंयुक्त उपसमुच्चय का $S_{1},\ldots ,S_{t}\subset [n]$ ऐसा कि, किसी भी उपसमुच्चय के लिए $S_{i}$, के बिट्स फ़्लिप करना $x$ तदनुसार $S_{i}$ का मान बदल देता है $f(x)$.

चूँकि $s(f)\leq bs(f)$ ब्लॉक संवेदनशीलता उपसमुच्चय के अधिक से अधिक संवेदनशीलता प्रतिशत प्रभाव डाले जाते हैं। इसके अतिरिक्त, ब्लॉक संवेदनशीलता बहुपद रूप से पहले चर्चा किए गए सम्मिश्रता माध्यमों से संबंधित है, उदाहरण के लिए, $bs(f)\leq D(f)=O(bs(f)^{4})$ ब्लॉक-संवेदनशीलता का परिचय विवरण वाले निसान के पेपर में यह दिखाया गया है, इसलिए, $bs(f)=O(s(f)^{c})$ कुछ अनुमान के लिए संवेदनशीलता अनुमान $c$ को दोबारा दर्शाया जा सकता है, 1992 में, निसान और सेज़ादी ने यह अनुमान लगाया $c=2$ पर्याप्त है। यह सख्त होगा, क्योंकि रुबिनस्टीन ने 1995 में संवेदनशीलता और ब्लॉक संवेदनशीलता के बीच एक द्विघात भिन्नाव दिखाया था।

जुलाई 2019 में, अनुमान प्रारंभ होने के 27 साल पश्चात, एमोरी विश्वविद्यालय के हाओ हुआंग ने संवेदनशीलता अनुमान सिद्ध किया, $bs(f)=O(s(f)^{4})$यह दिखाते हैं। यह प्रमाण विशेष रूप से संक्षिप्त है, इस कथन को दो पृष्ठों में सिद्ध करता है, जब संवेदनशीलता अनुमान की दिशा में पूर्व प्रगति सीमित थी।

ज्ञात परिणामों का सारांश

अक्टूबर 2020 तक सम्मिश्रता उपायों के लिए सबसे प्रसिद्ध पृथक्करण

	$D$	$R_{0}$	$R_{2}$	$C$	$RC$	$bs$	$s$	$Q_{0}$	$\deg$	$Q$	${\widetilde {\deg }}$
$D$		2	2, 3	2	2, 3	2, 3	3, 6	2, 3	2, 3	4	4
$R_{0}$	1		2	2	2, 3	2, 3	3, 6	2, 3	2, 3	3, 4	4
$R$	1	1		2	2, 3	2, 3	3, 6	1.5, 3	2, 3	3, 4	4
$C$	1	1	1, 2		2	2	2.22, 5	1.15, 3	1.63, 3	2, 4	2, 4
$RC$	1	1	1	1		1.5, 2	2, 4	1.15, 2	1.63, 2	2	2
$bs$	1	1	1	1	1		2, 4	1.15, 2	1.63, 2	2	2
$s$	1	1	1	1	1	1		1.15, 2	1.63, 2	2	2
$Q_{0}$	1	1.33, 2	1.33, 3	2	2, 3	2, 3	3, 6		2, 3	2, 4	4
$\deg$	1	1.33, 2	1.33, 2	2	2	2	2	1		2	2
$Q$	1	1	1	2	2, 3	2, 3	3, 6	1	2, 3		4
${\widetilde {\deg }}$	1	1	1	2	2	2	2	1	1	1

यह तालिका बूलियन फ़ंक्शन सम्मिश्रता माध्यमों के बीच भिन्नाव पर परिणामों का सारांश प्रस्तुत करती है। सम्मिश्रता के उपाय, क्रम में, नियतात्मक, शून्य-त्रुटि यादृच्छिक, दो-तरफा-त्रुटि यादृच्छिक, प्रमाणपत्र, यादृच्छिक प्रमाणपत्र, ब्लॉक संवेदनशीलता, संवेदनशीलता, उपयुक्त क्वांटम, डिग्री, क्वांटम और अनुमानित डिग्री सम्मिश्रताएं हैं।

में संख्या $A$-वीं पंक्ति और $B$-वां कॉलम घातांक $c$ पर परिबद्ध को दर्शाता है , $k$ जो सभी का न्यूनतम है, संतोषजनक $A(f)=O(B(f)^{k})$ सभी बूलियन फ़ंक्शंस के लिए $f$ हैं। उदाहरण के लिए, डी-वें पंक्ति और एस-वें कॉलम में प्रविष्टि 3, 6 है, $D(f)=O(\operatorname {s} (f)^{6+o(1)})$ सभी के लिए $f$, और $g$ ऐसा है, कि $D(g)=\Omega (\operatorname {s} (g)^{3-o(1)})$ वहाँ एक फ़ंक्शन उपलब्ध है।

यह भी देखें

• तुलना क्रम
• निर्णय वृक्ष
• आंडेरा-कार्प-रोसेनबर्ग अनुमान
• न्यूनतम फैले हुए वृक्ष#निर्णय वृक्ष

संदर्भ

सर्वेक्षण

• Buhrman, Harry; de Wolf, Ronald (2002), "Complexity Measures and Decision Tree Complexity: A Survey" (PDF), Theoretical Computer Science, 288 (1): 21–43, doi:10.1016/S0304-3975(01)00144-X

श्रेणी:अभिकलनात्मक सम्मिश्रता सिद्धांत श्रेणी:गणना के मॉडल श्रेणी:निर्णय वृक्ष