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

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

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

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

उदाहरण के लिए, एक निर्णय वृक्ष तर्क का उपयोग यह दिखाने के लिए किया जाता है, कि तुलनात्मक प्रकार $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$ न्यूनतम खोजने के लिए तुलना। (यहां सूचना-सैद्धांतिक तर्क केवल निम्न सीमा देता है $\log(n)$.) एक समान तर्क ऑर्डर आँकड़ों की गणना के लिए सामान्य निचली सीमा के लिए काम करता है।

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

रैखिक निर्णय वृक्ष उपरोक्त तुलनात्मक निर्णय वृक्षों को उन कंप्यूटिंग कार्यों के लिए सामान्यीकृत करते हैं जो वास्तविक सदिश स्थल लेते हैं $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$ ऐसा है कि $x_{i}=x_{j}$) गहराई के बीजगणितीय निर्णय वृक्ष की आवश्यकता है $\Omega (n\log(n))$. इसे पहली बार डोबकिन और लिप्टन द्वारा रैखिक निर्णय मॉडल के लिए दिखाया गया था। वे यह भी दिखाते हैं $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}$ (अर्थात्, सीमाबद्ध दोतरफा त्रुटि के साथ)।$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 के साथ (अर्थात् गणना करता है $f$ बिल्कुल)। $Q_{2}(f)$ और $Q_{E}(f)$ इन्हें आमतौर पर क्वांटम क्वेरी जटिलताओं के रूप में जाना जाता है, क्योंकि क्वांटम निर्णय वृक्ष की प्रत्यक्ष परिभाषा शास्त्रीय मामले की तुलना में अधिक जटिल है। यादृच्छिक मामले के समान, हम परिभाषित करते हैं $Q_{0}(f)$ और $Q_{1}(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$.

बूलियन फ़ंक्शन जटिलता उपायों के बीच संबंध

यह परिभाषाओं से तुरंत पता चलता है कि सभी के लिए $n$-बिट बूलियन फ़ंक्शन $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$. विपरीत दिशा में सर्वोत्तम ऊपरी सीमा ढूँढना क्वेरी जटिलता के क्षेत्र में एक प्रमुख लक्ष्य है।

इन सभी प्रकार की क्वेरी जटिलताएँ बहुपद से संबंधित हैं। ब्लम और इम्पाग्लियाज़ो, हार्टमैनिस और हेमचंद्र, और टार्डोस स्वतंत्र रूप से इसकी खोज की $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})$.इसलिए, कुछ लोगों के लिए संवेदनशीलता अनुमान को दोबारा दर्शाया जा सकता है $c$, $bs(f)=O(s(f)^{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

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