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

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

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

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

उदाहरण के लिए, एक निर्णय वृक्ष तर्क का उपयोग यह दिखाने के लिए किया जाता है, कि तुलनात्मक प्रकार $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})$, यह प्रमाण विशेष रूप से संक्षिप्त है, इस कथन को दो पृष्ठों में सिद्ध करता है, जब संवेदनशीलता अनुमान की दिशा में पूर्व प्रगति सीमित थी।

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

Best-known separations for complexity measures as of October 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

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