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

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

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

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

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

सॉर्टिंग के लिए ट्री और लोवर बाउंड का कम्पैरिज़न करें

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

उदाहरण के लिए, कई सॉर्टिंग कलन विधि कम्पैरिज़न सॉर्ट हैं, जिसका अर्थ है, कि वे मात्र इनपुट अनुक्रम के बारे में जानकारी प्राप्त करते हैं, $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$ से मेल खाता है जो बताता है कि आइटमों की पूरे प्रकार से ऑर्डर की गई सूची से इनपुट अनुक्रम को कैसे स्क्रैम्बल किया गया था। (इस परमुटेशन का इनवर्स, $\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)$ संभव है; ऐसी समस्या का पहला उदाहरण डीयूत्स्च और जोज़सा द्वारा खोजा गया था।

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

बूलियन फ़ंक्शन के लिए $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

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