डिसीजन ट्री मॉडल: Difference between revisions

Latest revision as of 09:42, 23 August 2023

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

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

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

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

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

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

उदाहरण के लिए, कई सॉर्टिंग कलन विधि कम्पैरिज़न सॉर्ट हैं, जिसका अर्थ है, कि वे मात्र इनपुट अनुक्रम के बारे में जानकारी प्राप्त करते हैं, $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))$ , इसलिए यह कम्पैरिज़न सॉर्टिंग कलन विधि के रन टाइम पर निम्न बाउंड है। इस स्थिति में, इस समय की कॉम्पलेक्सिटी वाले कई कम्पैरिज़न-सॉर्टिंग कलन विधि का अस्तित्व, जैसे मर्जसॉर्ट और हीपसॉर्ट, दर्शाता है कि बाउंड टाइट है।^[2]^: 91

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

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

रैखिक और बीजगणितीय डिसीजन ट्री

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

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

बूलियन डिसीजन ट्री कॉम्पलेक्सिटी

बूलियन डिसीजन ट्री के लिए, कार्य एन-बिट बूलियन फ़ंक्शन के मान की कम्प्यूटेशन करना है, $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$ उसे स्थापित किया गया है।^[9]

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

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

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

यह ध्यान रखना महत्वपूर्ण है, कि ये बहुपद संबंध मात्र कुल बूलियन कार्यों के लिए मान्य हैं। आंशिक बूलियन फ़ंक्शंस के लिए, $\{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)$ बदल देता है।^[13]

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

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

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

अक्टूबर 2020 तक कॉम्पलेक्सिटी उपायों के लिए सबसे प्रसिद्ध पृथक्करण^[16]
	$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)})$ वहाँ फ़ंक्शन उपलब्ध है।

यह भी देखें

कम्पैरिज़न क्रम
डिसीजन ट्री
आंडेरा-कार्प-रोसेनबर्ग अनुमान
न्यूनतम फैले हुए ट्री#डिसीजन ट्री

संदर्भ

↑ Ford, Lester R. Jr.; Johnson, Selmer M. (1959-05-01). "एक टूर्नामेंट समस्या". The American Mathematical Monthly. 66 (5): 387–389. doi:10.1080/00029890.1959.11989306. ISSN 0002-9890.
↑ ^2.0 ^2.1 एल्गोरिदम का परिचय. Cormen, Thomas H. (Third ed.). Cambridge, Mass.: MIT Press. 2009. ISBN 978-0-262-27083-0. OCLC 676697295.{{cite book}}: CS1 maint: others (link)
↑ Rabin, Michael O. (1972-12-01). "रैखिक रूपों की एक साथ सकारात्मकता सिद्ध करना". Journal of Computer and System Sciences (in English). 6 (6): 639–650. doi:10.1016/S0022-0000(72)80034-5. ISSN 0022-0000.
↑ Reingold, Edward M. (1972-10-01). "कुछ सेट एल्गोरिदम की इष्टतमता पर". Journal of the ACM. 19 (4): 649–659. doi:10.1145/321724.321730. ISSN 0004-5411. S2CID 18605212.
↑ Preparata, Franco P. (1985). Computational geometry : an introduction. Shamos, Michael Ian. New York: Springer-Verlag. ISBN 0-387-96131-3. OCLC 11970840.
↑ Ben-Or, Michael (1983-12-01). "बीजगणितीय संगणना वृक्षों के लिए निचली सीमाएँ". Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. STOC '83. New York, NY, USA: Association for Computing Machinery: 80–86. doi:10.1145/800061.808735. ISBN 978-0-89791-099-6. S2CID 1499957.
↑ Dobkin, David; Lipton, Richard J. (1976-06-01). "बहुआयामी खोज समस्याएँ". SIAM Journal on Computing. 5 (2): 181–186. doi:10.1137/0205015. ISSN 0097-5397.
↑ Michael Steele, J; Yao, Andrew C (1982-03-01). "बीजगणितीय निर्णय वृक्षों के लिए निचली सीमाएँ". Journal of Algorithms (in English). 3 (1): 1–8. doi:10.1016/0196-6774(82)90002-5. ISSN 0196-6774.
↑ ^9.0 ^9.1 Beals, R.; Buhrman, H.; Cleve, R.; Mosca, M.; de Wolf, R. (2001). "बहुपदों द्वारा क्वांटम निचली सीमाएँ". Journal of the ACM. 48 (4): 778–797. arXiv:quant-ph/9802049. doi:10.1145/502090.502097. S2CID 1078168.
↑ Blum, M.; Impagliazzo, R. (1987). "सामान्य दैवज्ञ और दैवज्ञ वर्ग". Proceedings of 18th IEEE FOCS. pp. 118–126.
↑ Hartmanis, J.; Hemachandra, L. (1987), "One-way functions, robustness, and non-isomorphism of NP-complete sets", Technical Report DCS TR86-796, Cornell University
↑ Tardos, G. (1989). "Query complexity, or why is it difficult to separate NP^A ∩ coNP^A from P^A by random oracles A?". Combinatorica. 9 (4): 385–392. doi:10.1007/BF02125350. S2CID 45372592.
↑ ^13.0 ^13.1 ^13.2 Nisan, N. (1989). "क्रू प्रैम और निर्णय वृक्ष". Proceedings of 21st ACM STOC. pp. 327–335.
↑ Kulkarni, R. and Tal, A. On Fractional Block Sensitivity. Electronic Colloquium on Computational Complexity (ECCC). Vol. 20. 2013.
↑ ^15.0 ^15.1 Ambainis, Andris; Balodis, Kaspars; Belovs, Aleksandrs; Lee, Troy; Santha, Miklos; Smotrovs, Juris (2017-09-04). "सूचक कार्यों के आधार पर क्वेरी जटिलता में पृथक्करण". Journal of the ACM. 64 (5): 32:1–32:24. arXiv:1506.04719. doi:10.1145/3106234. ISSN 0004-5411. S2CID 10214557.
↑ ^16.0 ^16.1 Aaronson, Scott; Ben-David, Shalev; Kothari, Robin; Rao, Shravas; Tal, Avishay (2020-10-23). "हुआंग की संवेदनशीलता प्रमेय की डिग्री बनाम अनुमानित डिग्री और क्वांटम निहितार्थ". arXiv:2010.12629 [quant-ph].
↑ Midrijanis, Gatis (2004), "Exact quantum query complexity for total Boolean functions", arXiv:quant-ph/0403168
↑ Midrijanis, Gatis (2005), "On Randomized and Quantum Query Complexities", arXiv:quant-ph/0501142
↑ Nisan, Noam; Szegedy, Mario (1992-07-01). "बूलियन की डिग्री पर वास्तविक बहुपद के रूप में कार्य करता है". Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing. STOC '92. Victoria, British Columbia, Canada: Association for Computing Machinery: 462–467. doi:10.1145/129712.129757. ISBN 978-0-89791-511-3. S2CID 6919144.
↑ Rubinstein, David (1995-06-01). "बूलियन फ़ंक्शंस की संवेदनशीलता बनाम ब्लॉक संवेदनशीलता". Combinatorica (in English). 15 (2): 297–299. doi:10.1007/BF01200762. ISSN 1439-6912. S2CID 41010711.
↑ Huang, Hao (2019). "हाइपरक्यूब के प्रेरित उपसमूह और संवेदनशीलता अनुमान का प्रमाण". Annals of Mathematics. 190 (3): 949–955. arXiv:1907.00847. doi:10.4007/annals.2019.190.3.6. ISSN 0003-486X. JSTOR 10.4007/annals.2019.190.3.6. S2CID 195767594.
↑ Klarreich, Erica. "दशकों पुराने कंप्यूटर विज्ञान अनुमान को दो पृष्ठों में हल किया गया". Quanta Magazine. Retrieved 2019-07-26.
↑ Hatami, Pooya; Kulkarni, Raghav; Pankratov, Denis (2011-06-22). "संवेदनशीलता अनुमान पर भिन्नताएँ". Theory of Computing (in English). 1: 1–27. doi:10.4086/toc.gs.2011.004. ISSN 1557-2862. S2CID 6918061.

सर्वेक्षण

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

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

[1] Ford, Lester R. Jr.; Johnson, Selmer M. (1959-05-01). "एक टूर्नामेंट समस्या". The American Mathematical Monthly. 66 (5): 387–389. doi:10.1080/00029890.1959.11989306. ISSN 0002-9890.

[CLRS-2] 2.0 ^2.1 एल्गोरिदम का परिचय. Cormen, Thomas H. (Third ed.). Cambridge, Mass.: MIT Press. 2009. ISBN 978-0-262-27083-0. OCLC 676697295.{{cite book}}: CS1 maint: others (link)

[3] Rabin, Michael O. (1972-12-01). "रैखिक रूपों की एक साथ सकारात्मकता सिद्ध करना". Journal of Computer and System Sciences (in English). 6 (6): 639–650. doi:10.1016/S0022-0000(72)80034-5. ISSN 0022-0000.

[4] Reingold, Edward M. (1972-10-01). "कुछ सेट एल्गोरिदम की इष्टतमता पर". Journal of the ACM. 19 (4): 649–659. doi:10.1145/321724.321730. ISSN 0004-5411. S2CID 18605212.

[5] Preparata, Franco P. (1985). Computational geometry : an introduction. Shamos, Michael Ian. New York: Springer-Verlag. ISBN 0-387-96131-3. OCLC 11970840.

[6] Ben-Or, Michael (1983-12-01). "बीजगणितीय संगणना वृक्षों के लिए निचली सीमाएँ". Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. STOC '83. New York, NY, USA: Association for Computing Machinery: 80–86. doi:10.1145/800061.808735. ISBN 978-0-89791-099-6. S2CID 1499957.

[7] Dobkin, David; Lipton, Richard J. (1976-06-01). "बहुआयामी खोज समस्याएँ". SIAM Journal on Computing. 5 (2): 181–186. doi:10.1137/0205015. ISSN 0097-5397.

[8] Michael Steele, J; Yao, Andrew C (1982-03-01). "बीजगणितीय निर्णय वृक्षों के लिए निचली सीमाएँ". Journal of Algorithms (in English). 3 (1): 1–8. doi:10.1016/0196-6774(82)90002-5. ISSN 0196-6774.

[Beals-9] 9.0 ^9.1 Beals, R.; Buhrman, H.; Cleve, R.; Mosca, M.; de Wolf, R. (2001). "बहुपदों द्वारा क्वांटम निचली सीमाएँ". Journal of the ACM. 48 (4): 778–797. arXiv:quant-ph/9802049. doi:10.1145/502090.502097. S2CID 1078168.

[BlumImpagliazzo_1995-10] Blum, M.; Impagliazzo, R. (1987). "सामान्य दैवज्ञ और दैवज्ञ वर्ग". Proceedings of 18th IEEE FOCS. pp. 118–126.

[HartmanisHemachandra-11] Hartmanis, J.; Hemachandra, L. (1987), "One-way functions, robustness, and non-isomorphism of NP-complete sets", Technical Report DCS TR86-796, Cornell University

[Tardos-12] Tardos, G. (1989). "Query complexity, or why is it difficult to separate NP^A ∩ coNP^A from P^A by random oracles A?". Combinatorica. 9 (4): 385–392. doi:10.1007/BF02125350. S2CID 45372592.

[Nisan-13] 13.0 ^13.1 ^13.2 Nisan, N. (1989). "क्रू प्रैम और निर्णय वृक्ष". Proceedings of 21st ACM STOC. pp. 327–335.

[KT13-14] Kulkarni, R. and Tal, A. On Fractional Block Sensitivity. Electronic Colloquium on Computational Complexity (ECCC). Vol. 20. 2013.

[ABBLSS17-15] 15.0 ^15.1 Ambainis, Andris; Balodis, Kaspars; Belovs, Aleksandrs; Lee, Troy; Santha, Miklos; Smotrovs, Juris (2017-09-04). "सूचक कार्यों के आधार पर क्वेरी जटिलता में पृथक्करण". Journal of the ACM. 64 (5): 32:1–32:24. arXiv:1506.04719. doi:10.1145/3106234. ISSN 0004-5411. S2CID 10214557.

[ABKRT-16] 16.0 ^16.1 Aaronson, Scott; Ben-David, Shalev; Kothari, Robin; Rao, Shravas; Tal, Avishay (2020-10-23). "हुआंग की संवेदनशीलता प्रमेय की डिग्री बनाम अनुमानित डिग्री और क्वांटम निहितार्थ". arXiv:2010.12629 [quant-ph].

[Midrijanis-17] Midrijanis, Gatis (2004), "Exact quantum query complexity for total Boolean functions", arXiv:quant-ph/0403168

[Midrijanis2-18] Midrijanis, Gatis (2005), "On Randomized and Quantum Query Complexities", arXiv:quant-ph/0501142

[NisanSzegedy-19] Nisan, Noam; Szegedy, Mario (1992-07-01). "बूलियन की डिग्री पर वास्तविक बहुपद के रूप में कार्य करता है". Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing. STOC '92. Victoria, British Columbia, Canada: Association for Computing Machinery: 462–467. doi:10.1145/129712.129757. ISBN 978-0-89791-511-3. S2CID 6919144.

[Rub95-20] Rubinstein, David (1995-06-01). "बूलियन फ़ंक्शंस की संवेदनशीलता बनाम ब्लॉक संवेदनशीलता". Combinatorica (in English). 15 (2): 297–299. doi:10.1007/BF01200762. ISSN 1439-6912. S2CID 41010711.

[Huang-21] Huang, Hao (2019). "हाइपरक्यूब के प्रेरित उपसमूह और संवेदनशीलता अनुमान का प्रमाण". Annals of Mathematics. 190 (3): 949–955. arXiv:1907.00847. doi:10.4007/annals.2019.190.3.6. ISSN 0003-486X. JSTOR 10.4007/annals.2019.190.3.6. S2CID 195767594.

[22] Klarreich, Erica. "दशकों पुराने कंप्यूटर विज्ञान अनुमान को दो पृष्ठों में हल किया गया". Quanta Magazine. Retrieved 2019-07-26.

[HKP-23] Hatami, Pooya; Kulkarni, Raghav; Pankratov, Denis (2011-06-22). "संवेदनशीलता अनुमान पर भिन्नताएँ". Theory of Computing (in English). 1: 1–27. doi:10.4086/toc.gs.2011.004. ISSN 1557-2862. S2CID 6918061.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

@@ Line 1: / Line 1: @@
 {{Short description|Model of computational complexity}}
-{{Use American English|date=January 2019}}
+[[कम्प्यूटेशनल जटिलता|कम्प्यूटेशनल कॉम्पलेक्सिटी]] में '''[[निर्णय वृक्ष|डिसीजन ट्री]] मॉडल''' [[गणना का मॉडल|कम्प्यूटेशन का मॉडल]] है जिसमें एल्गोरिथ्म को मूल रूप से डिसीजन ट्री माना जाता है, अर्थात, प्रश्नों या परीक्षणों का क्रम जो अनुकूली विधि से किया जाता है, इसलिए पिछले परीक्षणों के परिणाम अगले किए गए परीक्षणों को प्रभावित कर सकते हैं।
-[[कम्प्यूटेशनल जटिलता]] में [[निर्णय वृक्ष]] मॉडल [[गणना का मॉडल]] है जिसमें एक एल्गोरिथ्म को मूल रूप से एक निर्णय वृक्ष माना जाता है, अर्थात, प्रश्नों या परीक्षणों का एक क्रम जो अनुकूली तरीके से किया जाता है, इसलिए पिछले परीक्षणों के परिणाम अगले किए गए परीक्षणों को प्रभावित कर सकते हैं।
+सामान्यतः, इन परीक्षणों में परिणामों की छोटी संख्या होती है (जैसे यैस-नो प्रश्न) और इन्हें जल्दी से निष्पादित किया जा सकता है (जैसे, यूनिट कम्प्यूटेशनल कॉस्ट के साथ), इसलिए डिसीजन ट्री मॉडल में कलन विधि की सबसे वर्स्ट केस टाइम कॉम्पलेक्सिटी से मेल खाती है संबंधित डिसीजन ट्री की डेप्थ डिसीजन ट्री मॉडल में किसी समस्या या कलन विधि की कम्प्यूटेशनल कॉम्पलेक्सिटी की इस धारणा को इसकी डिसीजन ट्री कॉम्पलेक्सिटी या क्वेरी कॉम्पलेक्सिटी कहा जाता है।
-आम तौर पर, इन परीक्षणों में परिणामों की एक छोटी संख्या होती है (जैसे हां-नहीं प्रश्न) और इन्हें जल्दी से निष्पादित किया जा सकता है (जैसे, इकाई कम्प्यूटेशनल लागत के साथ), इसलिए निर्णय वृक्ष मॉडल में एल्गोरिदम की सबसे खराब स्थिति समय जटिलता से मेल खाती है संबंधित निर्णय वृक्ष की गहराई. निर्णय वृक्ष मॉडल में किसी समस्या या एल्गोरिदम की कम्प्यूटेशनल जटिलता की इस धारणा को इसकी निर्णय वृक्ष जटिलता या क्वेरी जटिलता कहा जाता है।
+डिसीजन ट्री मॉडल कम्प्यूटेशनल प्रॉब्लम्स और कलन विधि के कुछ क्लासेस के लिए कॉम्पलेक्सिटी सिद्धांत के लिए निम्न बाउंड स्थापित करने में सहायक होते हैं। कम्प्यूटेशनल मॉडल और क्वेरी कलन विधि के सॉर्ट के आधार पर डिसीजन ट्री मॉडल के कई प्रकार प्रस्तुत किए गए हैं।
-निर्णय वृक्ष मॉडल कम्प्यूटेशनल समस्याओं और एल्गोरिदम के कुछ वर्गों के लिए जटिलता सिद्धांत के लिए निचली सीमा स्थापित करने में सहायक होते हैं। कम्प्यूटेशनल मॉडल और क्वेरी एल्गोरिदम के प्रकार के आधार पर निर्णय वृक्ष मॉडल के कई प्रकार पेश किए गए हैं।
+उदाहरण के लिए, डिसीजन ट्री तर्क का उपयोग यह दिखाने के लिए किया जाता है, कि कम्पैरिज़न सॉर्ट <math>n</math> आइटम अवश्य होता है, और <math>n\log(n)</math> कम्पैरिज़न की जाती है। कम्पैरिज़न सॉर्टों के लिए, क्वेरी दो आइटम्स की कम्पैरिज़न है, a, b दो परिणामों के साथ (यह मानते हुए कि कोई आइटम समान नहीं हैं), या तो a<nowiki><b या a>b, इस मॉडल में कम्पैरिज़न सॉर्टों को डिसीजन ट्री के रूप में व्यक्त किया जा सकता है, क्योंकि ऐसे सॉर्टिंग कलन विधि मात्र इस सॉर्ट के प्रश्नों को निष्पादित करते हैं।</nowiki>
-उदाहरण के लिए, एक निर्णय वृक्ष तर्क का उपयोग यह दिखाने के लिए किया जाता है, कि तुलनात्मक प्रकार <math>n</math> आइटम अवश्य लेने होता है, <math>n\log(n)</math> तुलना की जाती है। तुलना प्रकारों के लिए, एक क्वेरी दो वस्तुओं की तुलना है, ए, बी दो परिणामों के साथ (यह मानते हुए कि कोई आइटम समान नहीं हैं), या तो ए<बी या ए>बी. इस मॉडल में तुलना प्रकारों को निर्णय वृक्ष के रूप में व्यक्त किया जा सकता है, क्योंकि ऐसे सॉर्टिंग एल्गोरिदम केवल इस प्रकार के प्रश्नों को निष्पादित करते हैं।
+==सॉर्टिंग के लिए ट्री और लोवर बाउंड का कम्पैरिज़न करें==
-==छंटाई के लिए पेड़ों और निचली सीमाओं की तुलना करें==
+सॉर्टिंग और अन्य समान प्रॉब्लम्स के लिए तथा कलन विधि को समझने के लिए अधिकांशतः डिसीजन ट्री का उपयोग किया जाता है, यह सबसे पहले फोर्ड और जॉनसन द्वारा किया गया है।<ref>{{Cite journal|last1=Ford|first1=Lester R. Jr.|last2=Johnson|first2=Selmer M.|date=1959-05-01|title=एक टूर्नामेंट समस्या|url=https://doi.org/10.1080/00029890.1959.11989306|journal=The American Mathematical Monthly|volume=66|issue=5|pages=387–389|doi=10.1080/00029890.1959.11989306|issn=0002-9890}}</ref>
-सॉर्टिंग और अन्य समान समस्याओं के लिए एल्गोरिदम को समझने के लिए अक्सर निर्णय वृक्षों का उपयोग किया जाता है, यह सबसे पहले फोर्ड और जॉनसन द्वारा किया गया है।<ref>{{Cite journal|last1=Ford|first1=Lester R. Jr.|last2=Johnson|first2=Selmer M.|date=1959-05-01|title=एक टूर्नामेंट समस्या|url=https://doi.org/10.1080/00029890.1959.11989306|journal=The American Mathematical Monthly|volume=66|issue=5|pages=387–389|doi=10.1080/00029890.1959.11989306|issn=0002-9890}}</ref>
+उदाहरण के लिए, कई सॉर्टिंग कलन विधि कम्पैरिज़न सॉर्ट हैं, जिसका अर्थ है, कि वे मात्र इनपुट अनुक्रम के बारे में जानकारी प्राप्त करते हैं, <math>x_1,x_2,\ldots,x_n</math> स्थानीय कम्पैरिज़नस के माध्यम से: परीक्षण करना कि क्या <math>x_i < x_j</math>, <math>x_i = x_j</math>, या <math>x_i > x_j</math>, यह मानते हुए कि क्रमबद्ध की जाने वाली सभी आइटम्स विशिष्ट और तुलनीय <math>x_i > x_j</math> हैं? इसे हाँ-या-नहीं प्रश्न के रूप में दोहराया जा सकता है।
-उदाहरण के लिए, कई सॉर्टिंग एल्गोरिदम तुलनात्मक सॉर्ट हैं, जिसका अर्थ है, कि वे केवल इनपुट अनुक्रम के बारे में जानकारी प्राप्त करते हैं, <math>x_1,x_2,\ldots,x_n</math> स्थानीय तुलनाओं के माध्यम से: परीक्षण करना कि क्या <math>x_i < x_j</math>, <math>x_i = x_j</math>, या <math>x_i > x_j</math>, यह मानते हुए कि क्रमबद्ध की जाने वाली सभी वस्तुएँ विशिष्ट और तुलनीय हैं, <math>x_i > x_j</math>है? इसे हाँ-या-नहीं प्रश्न के रूप में दोहराया जा सकता है।
+इन कलन विधि को बाइनरी डिसीजन ट्री के रूप में तैयार किया जा सकता है, जहां प्रश्न कम्पैरिज़न हैं, आंतरिक नोड प्रश्न से मेल खाता है, और नोड के चिल्ड्रेन अगली क्वेरी के अनुरूप होते हैं, जब प्रश्न का उत्तर हां या नहीं होता है। लीफ नोड्स के लिए, आउटपुट परमुटेशन से मेल खाता है, <math>\pi</math> जो बताता है, कि आइटमों की पूरी सॉर्ट से ऑर्डर की गई सूची से इनपुट अनुक्रम को कैसे खंगाला जाता है। लीफ नोड्स के लिए, आउटपुट परमुटेशन <math>\pi</math> से मेल खाता है जो बताता है कि आइटमों की पूरे प्रकार से ऑर्डर की गई सूची से इनपुट अनुक्रम को कैसे स्क्रैम्बल किया गया था। (इस परमुटेशन का इनवर्स, <math>\pi^{-1}</math>, इनपुट अनुक्रम को पुनः व्यवस्थित करता है।)
-इन एल्गोरिदम को बाइनरी निर्णय पेड़ों के रूप में तैयार किया जा सकता है, जहां प्रश्न तुलना हैं: एक आंतरिक नोड एक प्रश्न से मेल खाता है, और नोड के बच्चे अगली क्वेरी के अनुरूप होते हैं जब प्रश्न का उत्तर हां या नहीं होता है। लीफ नोड्स के लिए, आउटपुट क्रम[[परिवर्तन]] से मेल खाता है <math>\pi</math> यह बताता है कि आइटमों की पूरी तरह से ऑर्डर की गई सूची से इनपुट अनुक्रम को कैसे खंगाला गया था। (इस क्रमपरिवर्तन का उलटा, <math>\pi^{-1}</math>, इनपुट अनुक्रम को पुनः क्रमित करें।)
+कोई यह दिखा सकता है कि कम्पैरिज़न सॉर्टों का उपयोग अवश्य करना होता है, <math>\Omega(n\log(n))</math> सरल तर्क के माध्यम से कम्पैरिज़न कलन विधि के सही होने के लिए, इसे हर संभव परमुटेशन को आउटपुट करने में सक्षम होना चाहिए <math>n</math> तत्व; अन्यथा, कलन विधि इनपुट के रूप में उस विशेष परमुटेशन के लिए विफल हो जाता है। इसलिए, इसके संगत डिसीजन ट्री में कम से कम उतने ही लीफ़ होने होते हैं, जितने परमुटेशन हैं: <math>n!</math> पत्तियाँ। कम से कम कोई बाइनरी ट्री <math>n!</math> लीफ्स में कम से कम डेप्थ तो होती है, <math>\log_2(n!) = \Omega(n\log_2(n))</math>, इसलिए यह कम्पैरिज़न सॉर्टिंग कलन विधि के रन टाइम पर निम्न बाउंड है। इस स्थिति में, इस समय की कॉम्पलेक्सिटी वाले कई कम्पैरिज़न-सॉर्टिंग कलन विधि का अस्तित्व, जैसे [[मर्जसॉर्ट]] और [[हीपसॉर्ट]], दर्शाता है कि बाउंड टाइट है।<ref name="CLRS">{{Cite book|url=https://www.worldcat.org/oclc/676697295|title=एल्गोरिदम का परिचय|date=2009|publisher=MIT Press|others=Cormen, Thomas H.|isbn=978-0-262-27083-0|edition=Third |location=Cambridge, Mass.|oclc=676697295}}</ref>{{rp|91}}
-कोई यह दिखा सकता है कि तुलना प्रकार का उपयोग अवश्य करना चाहिए <math>\Omega(n\log(n))</math> एक सरल तर्क के माध्यम से तुलना: एक एल्गोरिदम के सही होने के लिए, इसे हर संभव क्रमपरिवर्तन को आउटपुट करने में सक्षम होना चाहिए <math>n</math> तत्व; अन्यथा, एल्गोरिदम इनपुट के रूप में उस विशेष क्रमपरिवर्तन के लिए विफल हो जाएगा। इसलिए, इसके संगत निर्णय वृक्ष में कम से कम उतने ही पत्ते होने चाहिए जितने क्रमपरिवर्तन हैं: <math>n!</math> पत्तियाँ। कम से कम कोई बाइनरी ट्री <math>n!</math> पत्तियों में कम से कम गहराई तो होती है <math>\log_2(n!) = \Omega(n\log_2(n))</math>, इसलिए यह तुलनात्मक सॉर्टिंग एल्गोरिदम के रन टाइम पर निचली सीमा है। इस मामले में, इस समय की जटिलता वाले कई तुलना-सॉर्टिंग एल्गोरिदम का अस्तित्व, जैसे [[मर्ज़ सॉर्ट]] और [[ढेर बनाएं और छांटें]], दर्शाता है कि सीमा तंग है।<ref name="CLRS">{{Cite book|url=https://www.worldcat.org/oclc/676697295|title=एल्गोरिदम का परिचय|date=2009|publisher=MIT Press|others=Cormen, Thomas H.|isbn=978-0-262-27083-0|edition=Third |location=Cambridge, Mass.|oclc=676697295}}</ref>{{rp|91}}
+यह तर्क क्वेरी के सॉर्ट के बारे में कुछ भी उपयोग नहीं करता है, इसलिए यह वास्तव में किसी भी सॉर्टिंग कलन विधि के लिए निम्न बाउंड सिद्ध करता है, जिसे बाइनरी डिसीजन ट्री के रूप में मॉडल किया जा सकता है। संक्षेप में, यह सूचना-सैद्धांतिक तर्क का पुनर्लेखन है, कि सही सॉर्टिंग कलन विधि को कम से कम सीखना होता है। <math>\log_2(n!)</math> इनपुट अनुक्रम के बारे में जानकारी के अंश है, परिणामस्वरूप, यह रेंडमाइज़्ड डिसीजन ट्री के लिए भी काम करता है।
-यह तर्क क्वेरी के प्रकार के बारे में कुछ भी उपयोग नहीं करता है, इसलिए यह वास्तव में किसी भी सॉर्टिंग एल्गोरिदम के लिए निचली सीमा साबित करता है जिसे बाइनरी निर्णय पेड़ के रूप में मॉडल किया जा सकता है। संक्षेप में, यह [[सूचना सिद्धांत]] | सूचना-सैद्धांतिक तर्क का पुनर्लेखन है कि एक सही सॉर्टिंग एल्गोरिदम को कम से कम सीखना चाहिए <math>\log_2(n!)</math> इनपुट अनुक्रम के बारे में जानकारी के अंश। परिणामस्वरूप, यह यादृच्छिक निर्णय वृक्षों के लिए भी काम करता है।
+अन्य डिसीजन ट्री निम्न बाउंड का उपयोग यह करता है, कि क्वेरी कम्पैरिज़न है। उदाहरण के लिए, सबसे छोटी संख्या ज्ञात करने के लिए मात्र कम्पैरिज़नस का उपयोग करने के कार्य पर विचार करें <math>n</math> एन नंबर है, जो सबसे छोटी संख्या निर्धारित करने से पहले, सबसे छोटी संख्या को छोड़कर प्रत्येक संख्या को कम से कम कम्पैरिज़न में "लूज़" (बड़ी कम्पैरिज़न करना) होता है। तो, इसमें कम से कम समय लगता है, न्यूनतम ज्ञात करने के लिए n-1 कम्पैरिज़न होती है। यहां सूचना-सैद्धांतिक तर्क मात्र निम्न बाउंड देता है, समान तर्क ऑर्डर आँकड़ों की कम्प्यूटेशन के लिए सामान्य निम्न बाउंड के लिए काम करता है।<ref name="CLRS" />{{rp|214}}
-अन्य निर्णय वृक्ष निचली सीमाओं का उपयोग यह करता है कि क्वेरी एक तुलना है। उदाहरण के लिए, सबसे छोटी संख्या ज्ञात करने के लिए केवल तुलनाओं का उपयोग करने के कार्य पर विचार करें <math>n</math> नंबर. सबसे छोटी संख्या निर्धारित करने से पहले, सबसे छोटी संख्या को छोड़कर प्रत्येक संख्या को कम से कम एक तुलना में हारना होगा (बड़ी से तुलना करें)। तो, इसमें कम से कम समय लगता है <math>n-1</math> न्यूनतम खोजने के लिए तुलना। (यहां सूचना-सैद्धांतिक तर्क केवल निम्न सीमा देता है <math>\log(n)</math>.) एक समान तर्क ऑर्डर आँकड़ों की गणना के लिए सामान्य निचली सीमा के लिए काम करता है।<ref name="CLRS" />{{rp|214}}
+==रैखिक और बीजगणितीय डिसीजन ट्री==
-==रैखिक और बीजगणितीय निर्णय वृक्ष==
+रैखिक डिसीजन ट्री उपरोक्त कम्पैरिज़न डिसीजन ट्री को वास्तविक सदिश लेने वाले अभिकलन कार्यों के लिए सामान्यीकृत करते हैं, <math>x \in \mathbb{R}^n</math> इनपुट के रूप में, रैखिक डिसीजन ट्री में परीक्षण रैखिक कार्य हैं, वास्तविक संख्याओं की विशेष पसंद के लिए <math>a_0, \dots, a_n</math>, का <math>a_0 + \textstyle\sum_{i = 1}^n a_ix_i</math>चिह्न आउटपुट करें, (इस मॉडल में कलन विधि मात्र आउटपुट के संकेत पर निर्भर हो सकते हैं।) कम्पैरिज़न ट्री रैखिक डिसीजन ट्री हैं, <math>x_i - x_j</math>क्योंकि बीच की कम्पैरिज़न <math>x_i</math> और <math>x_j</math> रैखिक फ़ंक्शन से मेल खाता है, इसकी परिभाषा से, रैखिक डिसीजन ट्री मात्र कार्य निर्दिष्ट कर सकते हैं, <math>f</math> जिसके फ़ाइबर का निर्माण आधे-स्थानों के संघों और प्रतिच्छेदनों को लेकर किया जा सकता है।
-रैखिक निर्णय वृक्ष उपरोक्त तुलनात्मक निर्णय वृक्षों को उन कंप्यूटिंग कार्यों के लिए सामान्यीकृत करते हैं जो वास्तविक [[सदिश स्थल]] लेते हैं <math>x \in \mathbb{R}^n</math> इनपुट के रूप में. रैखिक निर्णय वृक्षों में परीक्षण रैखिक कार्य हैं: वास्तविक संख्याओं की एक विशेष पसंद के लिए <math>a_0, \dots, a_n</math>, का चिन्ह आउटपुट करें <math>a_0 + \textstyle\sum_{i = 1}^n a_ix_i</math>. (इस मॉडल में एल्गोरिदम केवल आउटपुट के संकेत पर निर्भर हो सकते हैं।) तुलना वृक्ष रैखिक निर्णय वृक्ष हैं, क्योंकि बीच की तुलना <math>x_i</math> और <math>x_j</math> रैखिक फलन से मेल खाता है <math>x_i - x_j</math>. इसकी परिभाषा से, रैखिक निर्णय वृक्ष केवल कार्य निर्दिष्ट कर सकते हैं <math>f</math> जिसका फ़ाइबर (गणित) आधे-स्थानों के संघों और प्रतिच्छेदनों को लेकर बनाया जा सकता है।
+बीजगणितीय डिसीजन ट्री रैखिक डिसीजन ट्री का सामान्यीकरण है, जो परीक्षण कार्यों को डिग्री के बहुपद होने की अनुमति देते हैं। <math>d</math> ज्यामितीय रूप से, समष्टि को अर्ध-बीजगणितीय समूह (हाइपरसमतल का सामान्यीकरण) में विभाजित किया गया है।
-बीजगणितीय निर्णय वृक्ष रैखिक निर्णय वृक्षों का एक सामान्यीकरण है जो परीक्षण कार्यों को डिग्री के बहुपद होने की अनुमति देता है <math>d</math>. ज्यामितीय रूप से, अंतरिक्ष को अर्ध-बीजगणितीय सेट (हाइपरप्लेन का एक सामान्यीकरण) में विभाजित किया गया है।
+राबिन<ref>{{Cite journal|last=Rabin|first=Michael O.|date=1972-12-01|title=रैखिक रूपों की एक साथ सकारात्मकता सिद्ध करना|journal=Journal of Computer and System Sciences|language=en|volume=6|issue=6|pages=639–650|doi=10.1016/S0022-0000(72)80034-5|issn=0022-0000|doi-access=free}}</ref> और रींगोल्ड द्वारा परिभाषित ये डिसीजन ट्री मॉडल,<ref>{{Cite journal|last=Reingold|first=Edward M.|date=1972-10-01|title=कुछ सेट एल्गोरिदम की इष्टतमता पर|url=https://doi.org/10.1145/321724.321730|journal=Journal of the ACM|volume=19|issue=4|pages=649–659|doi=10.1145/321724.321730|s2cid=18605212|issn=0004-5411}}</ref> अधिकांशतः [[कम्प्यूटेशनल ज्यामिति]] में निम्न बाउंड सिद्ध करने के लिए उपयोग किए जाते हैं।<ref>{{Cite book|last=Preparata|first=Franco P.|url=https://www.worldcat.org/oclc/11970840|title=Computational geometry : an introduction|date=1985|publisher=Springer-Verlag|others=Shamos, Michael Ian.|isbn=0-387-96131-3|location=New York|oclc=11970840}}</ref> उदाहरण के लिए, बेन-ऑर ने उस तत्व की विशिष्टता (अभिकलन का कार्य) दिखाई <math>f: \mathbb{R}^n \to \{0,1\}</math>, कहां <math>f(x)</math> 0 है, यदि और मात्र तभी जब भिन्न-भिन्न निर्देशांक उपलब्ध हों <math>i, j</math> ऐसा है, <math>\Omega(n\log(n))</math> कि <math>x_i = x_j</math> को डेप्थ के बीजगणितीय डिसीजन ट्री की आवश्यकता होती है,<ref>{{Cite journal|last=Ben-Or|first=Michael|date=1983-12-01|title=बीजगणितीय संगणना वृक्षों के लिए निचली सीमाएँ|url=https://doi.org/10.1145/800061.808735|journal=Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing|series=STOC '83|location=New York, NY, USA|publisher=Association for Computing Machinery|pages=80–86|doi=10.1145/800061.808735|isbn=978-0-89791-099-6|s2cid=1499957|doi-access=free}}</ref> इसे पहली बार डोबकिन और लिप्टन द्वारा रैखिक डिसीजन मॉडल के लिए दिखाया जाता है।<ref>{{Cite journal|last1=Dobkin|first1=David|last2=Lipton|first2=Richard J.|date=1976-06-01|title=बहुआयामी खोज समस्याएँ|url=https://epubs.siam.org/doi/10.1137/0205015|journal=SIAM Journal on Computing|volume=5|issue=2|pages=181–186|doi=10.1137/0205015|issn=0097-5397}}</ref> वे यह भी दिखाते हैं, <math>n^2</math> नैपसैक समस्या पर रैखिक डिसीजन ट्री के लिए निम्न बाउंड, स्टील और याओ द्वारा बीजगणितीय डिसीजन ट्री के लिए सामान्यीकृत होता है।<ref>{{Cite journal|last1=Michael Steele|first1=J|last2=Yao|first2=Andrew C|date=1982-03-01|title=बीजगणितीय निर्णय वृक्षों के लिए निचली सीमाएँ|url=https://dx.doi.org/10.1016%2F0196-6774%2882%2990002-5|journal=Journal of Algorithms|language=en|volume=3|issue=1|pages=1–8|doi=10.1016/0196-6774(82)90002-5|issn=0196-6774}}</ref>
+== बूलियन डिसीजन ट्री कॉम्पलेक्सिटी ==
-ये निर्णय वृक्ष मॉडल, राबिन द्वारा परिभाषित<ref>{{Cite journal|last=Rabin|first=Michael O.|date=1972-12-01|title=रैखिक रूपों की एक साथ सकारात्मकता सिद्ध करना|journal=Journal of Computer and System Sciences|language=en|volume=6|issue=6|pages=639–650|doi=10.1016/S0022-0000(72)80034-5|issn=0022-0000|doi-access=free}}</ref> और रींगोल्ड,<ref>{{Cite journal|last=Reingold|first=Edward M.|date=1972-10-01|title=कुछ सेट एल्गोरिदम की इष्टतमता पर|url=https://doi.org/10.1145/321724.321730|journal=Journal of the ACM|volume=19|issue=4|pages=649–659|doi=10.1145/321724.321730|s2cid=18605212|issn=0004-5411}}</ref> अक्सर [[कम्प्यूटेशनल ज्यामिति]] में निचली सीमाओं को साबित करने के लिए उपयोग किया जाता है।<ref>{{Cite book|last=Preparata|first=Franco P.|url=https://www.worldcat.org/oclc/11970840|title=Computational geometry : an introduction|date=1985|publisher=Springer-Verlag|others=Shamos, Michael Ian.|isbn=0-387-96131-3|location=New York|oclc=11970840}}</ref> उदाहरण के लिए, बेन-ऑर ने उस तत्व की विशिष्टता (कंप्यूटिंग का कार्य) दिखाई <math>f: \mathbb{R}^n \to \{0,1\}</math>, कहाँ <math>f(x)</math> 0 है यदि और केवल यदि अलग-अलग निर्देशांक मौजूद हों <math>i, j</math> ऐसा है कि <math>x_i = x_j</math>) गहराई के बीजगणितीय निर्णय वृक्ष की आवश्यकता है <math>\Omega(n\log(n))</math>.<ref>{{Cite journal|last=Ben-Or|first=Michael|date=1983-12-01|title=बीजगणितीय संगणना वृक्षों के लिए निचली सीमाएँ|url=https://doi.org/10.1145/800061.808735|journal=Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing|series=STOC '83|location=New York, NY, USA|publisher=Association for Computing Machinery|pages=80–86|doi=10.1145/800061.808735|isbn=978-0-89791-099-6|s2cid=1499957|doi-access=free}}</ref> इसे पहली बार डोबकिन और लिप्टन द्वारा रैखिक निर्णय मॉडल के लिए दिखाया गया था।<ref>{{Cite journal|last1=Dobkin|first1=David|last2=Lipton|first2=Richard J.|date=1976-06-01|title=बहुआयामी खोज समस्याएँ|url=https://epubs.siam.org/doi/10.1137/0205015|journal=SIAM Journal on Computing|volume=5|issue=2|pages=181–186|doi=10.1137/0205015|issn=0097-5397}}</ref> वे यह भी दिखाते हैं <math>n^2</math> नैपसैक समस्या पर रैखिक निर्णय वृक्षों के लिए निचली सीमा, स्टील और याओ द्वारा बीजगणितीय निर्णय वृक्षों के लिए सामान्यीकृत।<ref>{{Cite journal|last1=Michael Steele|first1=J|last2=Yao|first2=Andrew C|date=1982-03-01|title=बीजगणितीय निर्णय वृक्षों के लिए निचली सीमाएँ|url=https://dx.doi.org/10.1016%2F0196-6774%2882%2990002-5|journal=Journal of Algorithms|language=en|volume=3|issue=1|pages=1–8|doi=10.1016/0196-6774(82)90002-5|issn=0196-6774}}</ref>
+बूलियन डिसीजन ट्री के लिए, कार्य एन-बिट [[बूलियन फ़ंक्शन]] के मान की कम्प्यूटेशन करना है, <math>f: \{0,1\}^n \to \{0,1\}</math>एक इनपुट के लिए <math>x \in \{0,1\}^n</math>, क्वेरीज़ इनपुट का थोड़ा सा पढ़ने से मेल खाती हैं, <math>x_i</math>, और <math>f(x)</math> आउटपुट है, प्रत्येक क्वेरी पिछली क्वेरी पर निर्भर हो सकती है। डिसीजन ट्री का उपयोग करने वाले कई सॉर्ट के कम्प्यूटेशनल मॉडल हैं, जिन पर विचार किया जा सकता है, कई कॉम्पलेक्सिटी धारणाओं को स्वीकार करते हुए, कॉम्पलेक्सिटी उपाय कहा जाता है।
-== बूलियन निर्णय वृक्ष जटिलताएँ ==
-बूलियन निर्णय वृक्षों के लिए, कार्य एन-बिट [[बूलियन फ़ंक्शन]] के मान की गणना करना है <math>f: \{0,1\}^n \to \{0,1\}</math> एक इनपुट के लिए <math>x \in \{0,1\}^n</math>. क्वेरीज़ इनपुट का थोड़ा सा पढ़ने से मेल खाती हैं, <math>x_i</math>, और आउटपुट है <math>f(x)</math>. प्रत्येक क्वेरी पिछली क्वेरी पर निर्भर हो सकती है। निर्णय पेड़ों का उपयोग करने वाले कई प्रकार के कम्प्यूटेशनल मॉडल हैं जिन पर विचार किया जा सकता है, कई जटिलता धारणाओं को स्वीकार करते हुए, जटिलता उपाय कहा जाता है।
+===डेटर्मीनिस्टिक डिसीजन ट्री===
+यदि डिसीजन ट्री का आउटपुट है, <math>f(x)</math> सभी के लिए <math>x\in \{0,1\}^n</math>, डिसीजन ट्री <math>f</math> को "कम्प्यूटेशन" करने के लिए कहा जाता है, किसी ट्री की डेप्थ, किसी लीफ़ तक पहुंचने और परिणाम प्राप्त होने से पहले होने वाली प्रश्नों की अधिकतम संख्या है। <math>D(f)</math>, डेटर्मीनिस्टिक डिसीजन ट्री कॉम्पलेक्सिटी <math>f</math> कम्प्यूटेशन करने वाले सभी डेटर्मीनिस्टिक डिसीजन ट्री <math>f</math> में सबसे छोटी डेप्थ है।
-===नियतात्मक निर्णय वृक्ष===
+===रेंडमाइज़्ड डिसीजन ट्री===
-यदि निर्णय वृक्ष का आउटपुट है <math>f(x)</math>, सभी के लिए <math>x\in \{0,1\}^n</math>, निर्णय वृक्ष की गणना करने के लिए कहा जाता है <math>f</math>. किसी पेड़ की गहराई, किसी पत्ते तक पहुंचने और परिणाम प्राप्त होने से पहले होने वाली प्रश्नों की अधिकतम संख्या है।<math>D(f)</math>, ''नियतात्मक निर्णय वृक्ष'' की जटिलता <math>f</math> गणना करने वाले सभी नियतात्मक निर्णय वृक्षों में सबसे छोटी गहराई है <math>f</math>.
+रेंडमाइज़्ड डिसीजन ट्री को परिभाषित करने का विधि ट्री में अतिरिक्त नोड्स जोड़ना है, <math>p_i</math>प्रत्येक को संभावना द्वारा कंट्रोल किया जाता है, अन्य समकक्ष परिभाषा इसे डेटर्मीनिस्टिक डिसीजन ट्री पर वितरण के रूप में परिभाषित करना है। इस दूसरी परिभाषा के आधार पर, रेंडमाइज़्ड ट्री की कॉम्पलेक्सिटी को अंतर्निहित वितरण के समर्थन में सभी ट्री के बीच सबसे बड़ी डेप्थ के रूप में परिभाषित किया गया है।
-===यादृच्छिक निर्णय वृक्ष===
+<math>R_2(f)</math> को सबसे कम डेप्थ वाले रेंडमाइज़्ड डिसीजन ट्री की कॉम्पलेक्सिटी के रूप में परिभाषित किया गया है, जिसका परिणाम है, <math>f(x)</math> कम से कम संभावना के साथ <math>2/3</math> सभी के लिए <math>x\in \{0,1\}^n</math> (अर्थात्, बाउंड 2-तरफा त्रुटि के साथ) होता है। <math>R_2(f)</math> [[मोंटे कार्लो एल्गोरिथ्म|मोंटे कार्लो]] रेंडमाइज़्ड डिसीजन-ट्री कॉम्पलेक्सिटी के रूप में जाना जाता है, क्योंकि परिणाम को दो-तरफा त्रुटि के साथ गलत होने की अनुमति है। [[लास वेगास]] डिसीजन-ट्री कॉम्पलेक्सिटी <math>R_0(f)</math> डिसीजन ट्री की अपेक्षित डेप्थ को मापता है, जो सही होना चाहिए (अर्थात, शून्य-त्रुटि है)। तरफा बाउंडेड-एरर संस्करण भी है, <math>R_1(f)</math>जिसे द्वारा दर्शाया गया है।
-यादृच्छिक निर्णय वृक्ष को परिभाषित करने का एक तरीका वृक्ष में अतिरिक्त नोड्स जोड़ना है, प्रत्येक को एक संभावना द्वारा नियंत्रित किया जाता है <math>p_i</math>. एक अन्य समकक्ष परिभाषा इसे नियतात्मक निर्णय वृक्षों पर वितरण के रूप में परिभाषित करना है। इस दूसरी परिभाषा के आधार पर, यादृच्छिक वृक्ष की जटिलता को अंतर्निहित वितरण के समर्थन में सभी पेड़ों के बीच सबसे बड़ी गहराई के रूप में परिभाषित किया गया है।<math>R_2(f)</math>को सबसे कम गहराई वाले यादृच्छिक निर्णय वृक्ष की जटिलता के रूप में परिभाषित किया गया है जिसका परिणाम है <math>f(x)</math> कम से कम संभावना के साथ <math>2/3</math> सभी के लिए <math>x\in \{0,1\}^n</math> (अर्थात्, सीमाबद्ध दोतरफा त्रुटि के साथ)।<math>R_2(f)</math>[[मोंटे कार्लो एल्गोरिथ्म]] को यादृच्छिक निर्णय-वृक्ष जटिलता के रूप में जाना जाता है, क्योंकि परिणाम को दो-तरफा त्रुटि के साथ गलत होने की अनुमति है। [[ लास वेगास एल्गोरिथ्म |लास वेगास एल्गोरिथ्म]] निर्णय-वृक्ष जटिलता<math>R_0(f)</math>निर्णय वृक्ष की ''अपेक्षित'' गहराई को मापता है जो सही होना चाहिए (यानी, शून्य-त्रुटि है)। एक तरफा बाउंडेड-एरर संस्करण भी है जिसे द्वारा दर्शाया गया है<math>R_1(f)</math>.
-===नॉनडेटेमिनिस्टिक निर्णय वृक्ष===
+===नॉनडेटर्मीनिस्टिक डिसीजन ट्री===
-किसी फ़ंक्शन की गैर-नियतात्मक निर्णय वृक्ष जटिलता को आमतौर पर उस फ़ंक्शन के [[प्रमाणपत्र (जटिलता)]] के रूप में जाना जाता है। यह इनपुट बिट्स की संख्या को मापता है जिसे एक गैर-नियतात्मक एल्गोरिदम को निश्चितता के साथ फ़ंक्शन का मूल्यांकन करने के लिए देखने की आवश्यकता होगी।
+किसी फ़ंक्शन की गैर-डेटर्मीनिस्टिक डिसीजन ट्री कॉम्पलेक्सिटी को सामान्यतः उस फ़ंक्शन की [[प्रमाणपत्र जटिलता|प्रमाणपत्र कॉम्पलेक्सिटी]] के रूप में जाना जाता है। यह इनपुट बिट्स की संख्या को मापता है, जिसे गैर-डेटर्मीनिस्टिक कलन विधि को निश्चितता के साथ फ़ंक्शन का मूल्यांकन करने के लिए देखने की आवश्यकता होती है।
-औपचारिक रूप से, प्रमाणपत्र जटिलता <math>f</math> पर <math>x</math> सूचकांकों के सबसे छोटे उपसमुच्चय का आकार है <math>S \subset [n]</math> ऐसा कि, सभी के लिए <math>y \in \{0,1\}^n</math>, अगर <math>y_i = x_i</math> सभी के लिए <math>i \in S</math>, तब <math>f(y) = f(x)</math>. की प्रमाणपत्र जटिलता <math>f</math> सभी की तुलना में अधिकतम प्रमाणपत्र जटिलता है <math>x</math>. अनुरूप धारणा जहां किसी को केवल 2/3 संभावना के साथ सत्यापनकर्ता के सही होने की आवश्यकता होती है, उसे दर्शाया गया है <math>RC(f)</math>.
+औपचारिक रूप से, प्रमाणपत्र कॉम्पलेक्सिटी <math>f</math> पर <math>x</math> सूचकांकों के सबसे छोटे उपसमुच्चय का बनावट है, <math>S \subset [n]</math> ऐसा कि, सभी के लिए <math>y \in \{0,1\}^n</math>, यदि <math>y_i = x_i</math> सभी के लिए <math>i \in S</math>, तब <math>f(y) = f(x)</math> है, की प्रमाणपत्र कॉम्पलेक्सिटी <math>f</math> सभी की कम्पैरिज़न में <math>x</math> अधिकतम प्रमाणपत्र कॉम्पलेक्सिटी है, अनुरूप धारणा जहां किसी को मात्र 2/3 संभावना के साथ सत्यापनकर्ता के सही होने की आवश्यकता होती है, <math>RC(f)</math> उसे दर्शाया गया है।
-===क्वांटम निर्णय वृक्ष===
+===क्वांटम डिसीजन ट्री===
-क्वांटम निर्णय वृक्ष जटिलता<math>Q_2(f)</math>सबसे कम गहराई वाले क्वांटम निर्णय वृक्ष की गहराई है जो परिणाम देती है <math>f(x)</math> कम से कम संभावना के साथ <math>2/3</math> सभी के लिए <math>x\in \{0,1\}^n </math>. अन्य मात्रा,<math>Q_E(f)</math>, को परिणाम देने वाले सबसे कम गहराई वाले क्वांटम निर्णय वृक्ष की गहराई के रूप में परिभाषित किया गया है <math>f(x)</math> सभी मामलों में प्रायिकता 1 के साथ (अर्थात् गणना करता है <math>f</math> बिल्कुल)। <math>Q_2(f)</math> और <math>Q_E(f)</math> इन्हें आमतौर पर क्वांटम क्वेरी जटिलताओं के रूप में जाना जाता है, क्योंकि क्वांटम निर्णय वृक्ष की प्रत्यक्ष परिभाषा शास्त्रीय मामले की तुलना में अधिक जटिल है। यादृच्छिक मामले के समान, हम परिभाषित करते हैं <math>Q_0(f)</math> और <math>Q_1(f)</math>.
+क्वांटम डिसीजन ट्री कॉम्पलेक्सिटी <math>Q_2(f)</math> सबसे कम डेप्थ वाले क्वांटम डिसीजन ट्री की डेप्थ है, जो परिणाम होता है, <math>f(x)</math> कम से कम संभावना के साथ 2 / 3 सभी के लिए <math>x\in \{0,1\}^n </math>, अन्य मात्रा, <math>Q_E(f)</math>, को परिणाम देने वाले सबसे कम डेप्थ वाले क्वांटम डिसीजन ट्री की डेप्थ के रूप में परिभाषित किया गया है, <math>f(x)</math> सभी स्थितियों में प्रायिकता 1 के साथ (अर्थात कम्प्यूटेशन करता है, <math>Q_2(f)</math> और <math>Q_E(f)</math> को सामान्यतः क्वांटम क्वेरी कॉम्पलेक्सिटीओं के रूप में जाना जाता है, क्योंकि क्वांटम डिसीजन ट्री की प्रत्यक्ष परिभाषा आधारित स्थिति की कम्पैरिज़न में अधिक काम्प्लेक्स है। रेंडमाइज़्ड स्थिति के समान, हम परिभाषित करते हैं।
-ये धारणाएँ आम तौर पर डिग्री और अनुमानित डिग्री की धारणाओं से बंधी होती हैं। की डिग्री <math>f</math>, निरूपित <math>\deg(f)</math>, किसी भी बहुपद की सबसे छोटी डिग्री है <math>p</math> संतुष्टि देने वाला <math>f(x) = p(x)</math> सभी के लिए <math>x \in \{0,1\}^n</math>. की अनुमानित डिग्री <math>f</math>, निरूपित <math>\widetilde{\deg}(f)</math>, किसी भी बहुपद की सबसे छोटी डिग्री है <math>p</math> संतुष्टि देने वाला <math>p(x) \in [0,1/3]</math> जब कभी भी <math>f(x) = 0</math> और <math>p(x) \in [2/3, 1]</math> जब कभी भी <math>f(x) = 1</math>.
+इसी प्रकार ये धारणाएँ सामान्यतः डिग्री और अनुमानित डिग्री की धारणाओं से बंधी होती हैं। डिग्री <math>f</math>, तथा निरूपित <math>\deg(f)</math>, किसी भी बहुपद की सबसे छोटी डिग्री है, <math>p</math> संतोषजनक <math>f(x) = p(x)</math> सभी के लिए <math>x \in \{0,1\}^n</math>, की अनुमानित डिग्री <math>f</math>, निरूपित <math>\widetilde{\deg}(f)</math>, किसी भी बहुपद की <math>p</math> संतोषजनक <math>p(x) \in [0,1/3]</math> जब भी <math>f(x) = 0</math> और <math>p(x) \in [2/3, 1]</math> जब भी <math>f(x) = 1</math> सबसे छोटी डिग्री है।
-बील्स एट अल. उसे स्थापित किया <math>Q_0(f) \geq \deg(f)/2</math> और <math>Q_2(f) \geq \widetilde{\deg}(f)/2</math>.<ref name="Beals">{{cite journal | last=Beals | first=R. |author2=Buhrman, H. |author3=Cleve, R. |author4=Mosca, M. |author5= de Wolf, R.  | year = 2001 | title= बहुपदों द्वारा क्वांटम निचली सीमाएँ| journal =Journal of the ACM | volume=48 | issue=4 | pages=778–797 | doi=10.1145/502090.502097|arxiv=quant-ph/9802049 | s2cid=1078168 }}</ref>
+बील्स एट अल. <math>Q_0(f) \geq \deg(f)/2</math> और <math>Q_2(f) \geq \widetilde{\deg}(f)/2</math> उसे स्थापित किया गया है।<ref name="Beals">{{cite journal | last=Beals | first=R. |author2=Buhrman, H. |author3=Cleve, R. |author4=Mosca, M. |author5= de Wolf, R.  | year = 2001 | title= बहुपदों द्वारा क्वांटम निचली सीमाएँ| journal =Journal of the ACM | volume=48 | issue=4 | pages=778–797 | doi=10.1145/502090.502097|arxiv=quant-ph/9802049 | s2cid=1078168 }}</ref>
-==बूलियन फ़ंक्शन जटिलता उपायों के बीच संबंध==
-यह परिभाषाओं से तुरंत पता चलता है कि सभी के लिए <math>n</math>-बिट बूलियन फ़ंक्शन <math>f</math>,<math>Q_2(f) \leq R_2(f) \leq R_1(f) \leq R_0(f) \leq D(f) \leq n</math>, और <math>Q_2(f) \leq Q_0(f) \leq D(f) \leq n</math>. विपरीत दिशा में सर्वोत्तम ऊपरी सीमा ढूँढना क्वेरी जटिलता के क्षेत्र में एक प्रमुख लक्ष्य है।
+==बूलियन फ़ंक्शन कॉम्पलेक्सिटी माध्यमों के बीच संबंध==
-इन सभी प्रकार की क्वेरी जटिलताएँ बहुपद से संबंधित हैं। ब्लम और इम्पाग्लियाज़ो,<ref name="BlumImpagliazzo 1995">{{cite conference | last = Blum | first=M. |author2=Impagliazzo, R. | title=सामान्य दैवज्ञ और दैवज्ञ वर्ग| year=1987 | book-title=Proceedings of 18th IEEE FOCS | pages=118–126}}</ref> हार्टमैनिस और हेमचंद्र,<ref name="HartmanisHemachandra">{{Citation | last1=Hartmanis | first1=J. | last2 = Hemachandra | first2=L. | year = 1987 | contribution=One-way functions, robustness, and non-isomorphism of NP-complete sets | title=Technical Report DCS TR86-796, Cornell University}}</ref> और टार्डोस<ref name="Tardos">{{cite journal | last=Tardos | first=G. | title=Query complexity, or why is it difficult to separate ''NP''<sup>''A''</sup>&nbsp;∩&nbsp;''coNP''<sup>''A''</sup> from ''P''<sup>''A''</sup> by random oracles ''A''? | journal=Combinatorica | year=1989 | pages=385–392|volume=9 | issue=4 | doi=10.1007/BF02125350| s2cid=45372592 }}</ref> स्वतंत्र रूप से इसकी खोज की <math>D(f) \leq R_0(f)^2</math>. [[ नोआम निसान |नोआम निसान]] ने पाया कि मोंटे कार्लो यादृच्छिक निर्णय वृक्ष जटिलता भी बहुपद रूप से नियतात्मक निर्णय वृक्ष जटिलता से संबंधित है: <math>D(f) = O(R_2(f)^3)</math>.<ref name="Nisan">{{cite conference | last=Nisan | first=N. | author-link = Noam Nisan | title=क्रू प्रैम और निर्णय वृक्ष| year=1989 | book-title=Proceedings of 21st ACM STOC | pages=327–335}}</ref> (निसान ने यह भी दिखाया <math>D(f) = O(R_1(f)^2)</math>.) मोंटे कार्लो और लास वेगास मॉडल के बीच एक कड़ा रिश्ता जाना जाता है: <math>R_0(f) = O(R_2(f)^2 \log R_2(f))</math>.<ref name="KT13">Kulkarni, R. and Tal, A. On Fractional Block Sensitivity. Electronic Colloquium on Computational Complexity (ECCC). Vol. 20. 2013.</ref> यह संबंध बहुगणितीय कारकों तक इष्टतम है।<ref name="ABBLSS17">{{Cite journal|last1=Ambainis|first1=Andris|last2=Balodis|first2=Kaspars|last3=Belovs|first3=Aleksandrs|last4=Lee|first4=Troy|last5=Santha|first5=Miklos|last6=Smotrovs|first6=Juris|date=2017-09-04|title=सूचक कार्यों के आधार पर क्वेरी जटिलता में पृथक्करण|url=https://doi.org/10.1145/3106234|journal=Journal of the ACM|volume=64|issue=5|pages=32:1–32:24|doi=10.1145/3106234|arxiv=1506.04719|s2cid=10214557|issn=0004-5411}}</ref> क्वांटम निर्णय वृक्ष जटिलताओं के लिए, <math>D(f) = O(Q_2(f)^4)</math>, और यह सीमा कड़ी है।<ref name="ABKRT">{{cite arXiv|last1=Aaronson|first1=Scott|last2=Ben-David|first2=Shalev|last3=Kothari|first3=Robin|last4=Rao|first4=Shravas|last5=Tal|first5=Avishay|date=2020-10-23|title=हुआंग की संवेदनशीलता प्रमेय की डिग्री बनाम अनुमानित डिग्री और क्वांटम निहितार्थ|class=quant-ph|eprint=2010.12629}}</ref><ref name="ABBLSS17"/>मिड्रिजनिस ने वह दिखाया <math>D(f) = O(Q_0(f)^3)</math>,<ref name="Midrijanis">{{cite arXiv | last=Midrijanis | first=Gatis | year = 2004 | eprint=quant-ph/0403168 |mode=cs2| title=Exact quantum query complexity for total Boolean functions }}</ref><ref name="Midrijanis2">{{cite arXiv | last=Midrijanis | first=Gatis | year = 2005  | eprint=quant-ph/0501142 |mode=cs2| title=On Randomized and Quantum Query Complexities }}</ref> बील्स एट अल के कारण चतुर्थक सीमा में सुधार।<ref name="Beals"/>
+यह परिभाषाओं से तुरंत पता चलता है कि <math>f</math>,<math>Q_2(f) \leq R_2(f) \leq R_1(f) \leq R_0(f) \leq D(f) \leq n</math>, और <math>Q_2(f) \leq Q_0(f) \leq D(f) \leq n</math> सभी के लिए <math>n</math>-बिट बूलियन फ़ंक्शन है, विपरीत दिशा में सर्वोत्तम ऊपरी सीमा ढूँढना क्वेरी कॉम्पलेक्सिटी के क्षेत्र में प्रमुख लक्ष्य है।
-यह ध्यान रखना महत्वपूर्ण है कि ये बहुपद संबंध केवल कुल बूलियन कार्यों के लिए मान्य हैं। [[कुल कार्य]] के लिए, इसमें एक डोमेन का एक उपसमूह होता है <math>\{0,1\}^n</math>, के बीच एक घातीय अलगाव <math>Q_0(f)</math> और <math>D(f)</math> संभव है; ऐसी समस्या का पहला उदाहरण Deutsch-Jozsa एल्गोरिथम द्वारा खोजा गया था।
+इन सभी सॉर्ट की क्वेरी कॉम्पलेक्सिटीएँ बहुपद से संबंधित हैं। ब्लम और इम्पाग्लियाज़ो,<ref name="BlumImpagliazzo 1995">{{cite conference | last = Blum | first=M. |author2=Impagliazzo, R. | title=सामान्य दैवज्ञ और दैवज्ञ वर्ग| year=1987 | book-title=Proceedings of 18th IEEE FOCS | pages=118–126}}</ref> हार्टमैनिस और हेमचंद्र,<ref name="HartmanisHemachandra">{{Citation | last1=Hartmanis | first1=J. | last2 = Hemachandra | first2=L. | year = 1987 | contribution=One-way functions, robustness, and non-isomorphism of NP-complete sets | title=Technical Report DCS TR86-796, Cornell University}}</ref> और टार्डोस<ref name="Tardos">{{cite journal | last=Tardos | first=G. | title=Query complexity, or why is it difficult to separate ''NP''<sup>''A''</sup>&nbsp;∩&nbsp;''coNP''<sup>''A''</sup> from ''P''<sup>''A''</sup> by random oracles ''A''? | journal=Combinatorica | year=1989 | pages=385–392|volume=9 | issue=4 | doi=10.1007/BF02125350| s2cid=45372592 }}</ref> ने स्वतंत्र रूप से इसकी खोज की <math>D(f) \leq R_0(f)^2</math>, [[नोम निसान]] ने पाया कि<math>D(f) = O(R_2(f)^3)</math> मोंटे कार्लो रेंडमाइज़्ड डिसीजन ट्री कॉम्पलेक्सिटी भी बहुपद रूप से डेटर्मीनिस्टिक डिसीजन ट्री कॉम्पलेक्सिटी से संबंधित है: <ref name="Nisan">{{cite conference | last=Nisan | first=N. | author-link = Noam Nisan | title=क्रू प्रैम और निर्णय वृक्ष| year=1989 | book-title=Proceedings of 21st ACM STOC | pages=327–335}}</ref> (निसान ने यह भी दिखाया <math>D(f) = O(R_1(f)^2)</math>) मोंटे कार्लो और <math>R_0(f) = O(R_2(f)^2 \log R_2(f))</math> लास वेगास मॉडल के बीच मजबूत संबंध ज्ञात है,<ref name="KT13">Kulkarni, R. and Tal, A. On Fractional Block Sensitivity. Electronic Colloquium on Computational Complexity (ECCC). Vol. 20. 2013.</ref> यह संबंध बहुगणितीय कारकों तक इष्टतम है।<ref name="ABBLSS17">{{Cite journal|last1=Ambainis|first1=Andris|last2=Balodis|first2=Kaspars|last3=Belovs|first3=Aleksandrs|last4=Lee|first4=Troy|last5=Santha|first5=Miklos|last6=Smotrovs|first6=Juris|date=2017-09-04|title=सूचक कार्यों के आधार पर क्वेरी जटिलता में पृथक्करण|url=https://doi.org/10.1145/3106234|journal=Journal of the ACM|volume=64|issue=5|pages=32:1–32:24|doi=10.1145/3106234|arxiv=1506.04719|s2cid=10214557|issn=0004-5411}}</ref> क्वांटम डिसीजन ट्री कॉम्पलेक्सिटीओं के लिए, <math>D(f) = O(Q_2(f)^4)</math>और यह बाउंड कड़ी है।<ref name="ABKRT">{{cite arXiv|last1=Aaronson|first1=Scott|last2=Ben-David|first2=Shalev|last3=Kothari|first3=Robin|last4=Rao|first4=Shravas|last5=Tal|first5=Avishay|date=2020-10-23|title=हुआंग की संवेदनशीलता प्रमेय की डिग्री बनाम अनुमानित डिग्री और क्वांटम निहितार्थ|class=quant-ph|eprint=2010.12629}}</ref><ref name="ABBLSS17"/> <math>D(f) = O(Q_0(f)^3)</math> मिड्रिजनिस ने वह दिखाया है।<ref name="Midrijanis">{{cite arXiv | last=Midrijanis | first=Gatis | year = 2004 | eprint=quant-ph/0403168 |mode=cs2| title=Exact quantum query complexity for total Boolean functions }}</ref><ref name="Midrijanis2">{{cite arXiv | last=Midrijanis | first=Gatis | year = 2005  | eprint=quant-ph/0501142 |mode=cs2| title=On Randomized and Quantum Query Complexities }}</ref> बील्स एट अल के कारण चतुर्थक सीमा में सुधार होता है।<ref name="Beals"/>
+यह ध्यान रखना महत्वपूर्ण है, कि ये बहुपद संबंध मात्र कुल बूलियन कार्यों के लिए मान्य हैं। आंशिक बूलियन फ़ंक्शंस के लिए, <math>\{0,1\}^n</math> जिसमें डोमेन का सबसमूह होता है, कि बीच घातांकीय पृथक्करण <math>Q_0(f)</math> और <math>D(f)</math> संभव है; ऐसी समस्या का पहला उदाहरण डीयूत्स्च और जोज़सा द्वारा खोजा गया था।
 === संवेदनशीलता अनुमान ===
-बूलियन फ़ंक्शन के लिए <math>f: \{0,1\}^n \to \{0,1\}</math>, की संवेदनशीलता <math>f</math> की अधिकतम संवेदनशीलता के रूप में परिभाषित किया गया है <math>f</math> कुल मिलाकर <math>x</math>, जहां की संवेदनशीलता <math>f</math> पर <math>x</math> में एकल-बिट परिवर्तनों की संख्या है <math>x</math> जिससे इसका मान बदल जाता है <math>f(x)</math>. संवेदनशीलता बूलियन फ़ंक्शंस के विश्लेषण से कुल प्रभाव की धारणा से संबंधित है, जो सभी पर औसत संवेदनशीलता के बराबर है <math>x</math>.
+बूलियन फ़ंक्शन के लिए <math>f: \{0,1\}^n \to \{0,1\}</math>, की संवेदनशीलता <math>f</math> को अधिकतम संवेदनशीलता के रूप में परिभाषित किया गया है, <math>f</math> सब से ऊपर <math>x</math>, जहां की संवेदनशीलता <math>f</math> पर <math>x</math> एकल-बिट परिवर्तित की संख्या है, <math>x</math> जो <math>f(x)</math> का मान बदलता है, संवेदनशीलता बूलियन फ़ंक्शंस के विश्लेषण से कुल प्रभाव की धारणा से संबंधित है, <math>x</math> जो सभी पर औसत संवेदनशीलता के समतुल्य है।
+संवेदनशीलता अनुमान वह अनुमान है, कि संवेदनशीलता बहुपद रूप से क्वेरी कॉम्पलेक्सिटी से संबंधित है, अर्थात् घातांक विद्यमान है, <math>c, c'</math> ऐसा कि, सभी के लिए <math>f</math>, <math>D(f) = O(s(f)^c)</math> और <math>s(f) = O(D(f)^{c'})</math>है, <math>s(f) \leq D(f)</math> कोई साधारण तर्क के माध्यम से यह दिखा सकता है, इसलिए अनुमान विशेष रूप से संवेदनशीलता के लिए निम्न सीमा खोजने के बारे में चिंतित है। चूंकि पहले चर्चा की गई सभी कॉम्पलेक्सिटी माप बहुपद से संबंधित हैं, इसलिए उपयुक्त सॉर्ट की कॉम्पलेक्सिटी माप प्रासंगिक नहीं है। चूंकि, इसे सामान्यतः ब्लॉक संवेदनशीलता के साथ संवेदनशीलता से संबंधित प्रश्न के रूप में व्यक्त किया जाता है।
-संवेदनशीलता अनुमान वह अनुमान है कि संवेदनशीलता बहुपद रूप से क्वेरी जटिलता से संबंधित है; अर्थात् घातांक विद्यमान है <math>c, c'</math> ऐसा कि, सभी के लिए <math>f</math>, <math>D(f) = O(s(f)^c)</math> और <math>s(f) = O(D(f)^{c'})</math>. कोई एक साधारण तर्क के माध्यम से यह दिखा सकता है <math>s(f) \leq D(f)</math>, इसलिए अनुमान विशेष रूप से संवेदनशीलता के लिए निचली सीमा खोजने के बारे में चिंतित है। चूंकि पहले चर्चा की गई सभी जटिलता माप बहुपद से संबंधित हैं, इसलिए सटीक प्रकार की जटिलता माप प्रासंगिक नहीं है। हालाँकि, इसे आम तौर पर ब्लॉक संवेदनशीलता के साथ संवेदनशीलता से संबंधित प्रश्न के रूप में व्यक्त किया जाता है।
+की ब्लॉक संवेदनशीलता <math>f</math>, निरूपित <math>bs(f)</math>, की अधिकतम ब्लॉक संवेदनशीलता के रूप में परिभाषित किया गया है, <math>f</math> सब से ऊपर <math>x</math> की ब्लॉक संवेदनशीलता <math>f</math> पर <math>x</math> अधिकतम संख्या है, <math>t</math> असंयुक्त उपसमुच्चय का <math>S_1, \ldots, S_t \subset [n]</math> ऐसा कि, किसी भी उपसमुच्चय के लिए <math>S_i</math>, के बिट्स फ़्लिप करना <math>x</math> तदनुसार <math>S_i</math> का मान <math>f(x)</math> बदल देता है।<ref name="Nisan"/>
-की ब्लॉक संवेदनशीलता <math>f</math>, निरूपित <math>bs(f)</math>, की अधिकतम ब्लॉक संवेदनशीलता के रूप में परिभाषित किया गया है <math>f</math> कुल मिलाकर <math>x</math>. की ब्लॉक संवेदनशीलता <math>f</math> पर <math>x</math> अधिकतम संख्या है <math>t</math> असंयुक्त उपसमुच्चय का <math>S_1, \ldots, S_t \subset [n]</math> ऐसा कि, किसी भी उपसमुच्चय के लिए <math>S_i</math>, के बिट्स फ़्लिप करना <math>x</math> तदनुसार <math>S_i</math> का मान बदल देता है <math>f(x)</math>.<ref name="Nisan"/>
+चूँकि <math>s(f) \leq bs(f)</math> ब्लॉक संवेदनशीलता उपसमुच्चय के अधिक से अधिक संवेदनशीलता प्रतिशत प्रभाव डाले जाते हैं। इसके अतिरिक्त, ब्लॉक संवेदनशीलता बहुपद रूप से पहले चर्चा किए गए कॉम्पलेक्सिटी माध्यमों से संबंधित है, उदाहरण के लिए, <math>bs(f) \leq D(f) = O(bs(f)^4)</math> ब्लॉक-संवेदनशीलता का परिचय विवरण वाले निसान के पेपर में यह दिखाया गया है,<ref name="Nisan"/> इसलिए, <math>bs(f)=O(s(f)^c)</math> कुछ अनुमान के लिए संवेदनशीलता अनुमान <math>c</math> को दोबारा दर्शाया जा सकता है, 1992 में, निसान और सेज़ादी ने यह अनुमान लगाया <math>c = 2</math> पर्याप्त है।<ref name="NisanSzegedy">{{Cite journal|last1=Nisan|first1=Noam|last2=Szegedy|first2=Mario|date=1992-07-01|title=बूलियन की डिग्री पर वास्तविक बहुपद के रूप में कार्य करता है|url=https://doi.org/10.1145/129712.129757|journal=Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing|series=STOC '92|location=Victoria, British Columbia, Canada|publisher=Association for Computing Machinery|pages=462–467|doi=10.1145/129712.129757|isbn=978-0-89791-511-3|s2cid=6919144|doi-access=free}}</ref> यह सख्त होगा, क्योंकि रुबिनस्टीन ने 1995 में संवेदनशीलता और ब्लॉक संवेदनशीलता के बीच द्विघात भिन्नाव दिखाया था।<ref name="Rub95">{{Cite journal|last=Rubinstein|first=David|date=1995-06-01|title=बूलियन फ़ंक्शंस की संवेदनशीलता बनाम ब्लॉक संवेदनशीलता|url=https://doi.org/10.1007/BF01200762|journal=Combinatorica|language=en|volume=15|issue=2|pages=297–299|doi=10.1007/BF01200762|s2cid=41010711|issn=1439-6912}}</ref>
-चूँकि ब्लॉक संवेदनशीलता उपसमुच्चय के अधिक विकल्पों पर अधिकतम प्रभाव डालती है, <math>s(f) \leq bs(f)</math>. इसके अलावा, ब्लॉक संवेदनशीलता बहुपद रूप से पहले चर्चा किए गए जटिलता उपायों से संबंधित है; उदाहरण के लिए, ब्लॉक-संवेदनशीलता का परिचय देने वाले निसान के पेपर ने यह दिखाया <math>bs(f) \leq D(f) = O(bs(f)^4)</math>.<ref name="Nisan"/>इसलिए, कुछ लोगों के लिए संवेदनशीलता अनुमान को दोबारा दर्शाया जा सकता है <math>c</math>, <math>bs(f)=O(s(f)^c)</math>. 1992 में, निसान और सेजेडी ने यह अनुमान लगाया <math>c = 2</math> पर्याप्त.<ref name="NisanSzegedy">{{Cite journal|last1=Nisan|first1=Noam|last2=Szegedy|first2=Mario|date=1992-07-01|title=बूलियन की डिग्री पर वास्तविक बहुपद के रूप में कार्य करता है|url=https://doi.org/10.1145/129712.129757|journal=Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing|series=STOC '92|location=Victoria, British Columbia, Canada|publisher=Association for Computing Machinery|pages=462–467|doi=10.1145/129712.129757|isbn=978-0-89791-511-3|s2cid=6919144|doi-access=free}}</ref> यह कठिन होगा, क्योंकि 1995 में रुबिनस्टीन ने संवेदनशीलता और ब्लॉक संवेदनशीलता के बीच एक द्विघात अलगाव दिखाया था।<ref name="Rub95">{{Cite journal|last=Rubinstein|first=David|date=1995-06-01|title=बूलियन फ़ंक्शंस की संवेदनशीलता बनाम ब्लॉक संवेदनशीलता|url=https://doi.org/10.1007/BF01200762|journal=Combinatorica|language=en|volume=15|issue=2|pages=297–299|doi=10.1007/BF01200762|s2cid=41010711|issn=1439-6912}}</ref>
+जुलाई 2019 में, अनुमान प्रारंभ होने के 27 साल पश्चात, [[एमोरी विश्वविद्यालय]] के हाओ हुआंग ने संवेदनशीलता अनुमान सिद्ध किया, <math>bs(f) = O(s(f)^4)</math> यह दिखाते हैं।<ref name="Huang">{{Cite journal|last=Huang|first=Hao|date=2019|title=हाइपरक्यूब के प्रेरित उपसमूह और संवेदनशीलता अनुमान का प्रमाण|journal=Annals of Mathematics|volume=190|issue=3|pages=949–955|doi=10.4007/annals.2019.190.3.6|jstor=10.4007/annals.2019.190.3.6|arxiv=1907.00847|s2cid=195767594|issn=0003-486X}}</ref> यह प्रमाण विशेष रूप से संक्षिप्त है, इस कथन को दो पृष्ठों में सिद्ध करता है, जब संवेदनशीलता अनुमान की दिशा में पूर्व प्रगति सीमित थी।<ref>{{Cite web|last=Klarreich|first=Erica|title=दशकों पुराने कंप्यूटर विज्ञान अनुमान को दो पृष्ठों में हल किया गया|url=https://www.quantamagazine.org/mathematician-solves-computer-science-conjecture-in-two-pages-20190725/|access-date=2019-07-26|website=Quanta Magazine}}</ref><ref name="HKP">{{Cite journal|last1=Hatami|first1=Pooya|last2=Kulkarni|first2=Raghav|last3=Pankratov|first3=Denis|date=2011-06-22|title=संवेदनशीलता अनुमान पर भिन्नताएँ|url=http://www.theoryofcomputing.org/articles/gs004|journal=Theory of Computing|volume=1|language=EN|pages=1–27|doi=10.4086/toc.gs.2011.004|s2cid=6918061|issn=1557-2862|doi-access=free}}</ref>
-जुलाई 2019 में, अनुमान शुरू होने के 27 साल बाद, [[एमोरी विश्वविद्यालय]] के हाओ हुआंग (गणितज्ञ) ने संवेदनशीलता अनुमान साबित किया, यह दिखाते हुए <math>bs(f) = O(s(f)^4)</math>.<ref name="Huang">{{Cite journal|last=Huang|first=Hao|date=2019|title=हाइपरक्यूब के प्रेरित उपसमूह और संवेदनशीलता अनुमान का प्रमाण|journal=Annals of Mathematics|volume=190|issue=3|pages=949–955|doi=10.4007/annals.2019.190.3.6|jstor=10.4007/annals.2019.190.3.6|arxiv=1907.00847|s2cid=195767594|issn=0003-486X}}</ref> यह प्रमाण विशेष रूप से संक्षिप्त है, इस कथन को दो पृष्ठों में सिद्ध करता है जब संवेदनशीलता अनुमान की दिशा में पूर्व प्रगति सीमित थी।<ref>{{Cite web|last=Klarreich|first=Erica|title=दशकों पुराने कंप्यूटर विज्ञान अनुमान को दो पृष्ठों में हल किया गया|url=https://www.quantamagazine.org/mathematician-solves-computer-science-conjecture-in-two-pages-20190725/|access-date=2019-07-26|website=Quanta Magazine}}</ref><ref name="HKP">{{Cite journal|last1=Hatami|first1=Pooya|last2=Kulkarni|first2=Raghav|last3=Pankratov|first3=Denis|date=2011-06-22|title=संवेदनशीलता अनुमान पर भिन्नताएँ|url=http://www.theoryofcomputing.org/articles/gs004|journal=Theory of Computing|volume=1|language=EN|pages=1–27|doi=10.4086/toc.gs.2011.004|s2cid=6918061|issn=1557-2862|doi-access=free}}</ref>
 === ज्ञात परिणामों का सारांश{{mw-datatable}} ===
 {| class="wikitable mw-datatable"
-|+ Best-known separations for complexity measures {{As of|2020|10|lc=y}}<ref name="ABKRT"/>
+|+ अक्टूबर 2020 तक कॉम्पलेक्सिटी उपायों के लिए सबसे प्रसिद्ध पृथक्करण<ref name="ABKRT"/>
 !
 ! <math>D</math>
@@ Line 119: / Line 121: @@
 | 1 || 1 || 1 || 2 || 2 || 2 || 2 || 1 || 1 || 1 ||
 |}
-यह तालिका बूलियन फ़ंक्शन जटिलता उपायों के बीच अलगाव पर परिणामों का सारांश प्रस्तुत करती है। जटिलता के उपाय, क्रम में, नियतात्मक, शून्य-त्रुटि यादृच्छिक, दो-तरफा-त्रुटि यादृच्छिक, प्रमाणपत्र, यादृच्छिक प्रमाणपत्र, ब्लॉक संवेदनशीलता, संवेदनशीलता, सटीक क्वांटम, डिग्री, क्वांटम और अनुमानित डिग्री जटिलताएं हैं।
+यह तालिका बूलियन फ़ंक्शन कॉम्पलेक्सिटी माध्यमों के बीच भिन्नाव पर परिणामों का सारांश प्रस्तुत करती है। कॉम्पलेक्सिटी के उपाय, क्रम में, डेटर्मीनिस्टिक, शून्य-त्रुटि रेंडमाइज़्ड, दो-तरफा-त्रुटि रेंडमाइज़्ड, प्रमाणपत्र, रेंडमाइज़्ड प्रमाणपत्र, ब्लॉक संवेदनशीलता, संवेदनशीलता, उपयुक्त क्वांटम, डिग्री, क्वांटम और अनुमानित डिग्री कॉम्पलेक्सिटी हैं।
-में संख्या <math>A</math>-वीं पंक्ति और <math>B</math>-वां कॉलम घातांक पर सीमा को दर्शाता है <math>c</math>, जो सभी में न्यूनतम है <math>k</math> संतुष्टि देने वाला <math>A(f) = O(B(f)^k)</math> सभी बूलियन फ़ंक्शंस के लिए <math>f</math>. उदाहरण के लिए, डी-वें पंक्ति और एस-वें कॉलम में प्रविष्टि 3, 6 है, इसलिए <math>D(f) = O(\operatorname{s}(f)^{6 + o(1)})</math> सभी के लिए <math>f</math>, और वहां एक फ़ंक्शन मौजूद है <math>g</math> ऐसा है कि <math>D(g) = \Omega(\operatorname{s}(g)^{3 - o(1)})</math>.
+इसी प्रकार संख्या में <math>A</math>-वीं पंक्ति और <math>B</math>-वां कॉलम घातांक <math>c</math> पर बाउंड को दर्शाता है , <math>k</math> जो सभी का न्यूनतम है, संतोषजनक <math>A(f) = O(B(f)^k)</math> सभी बूलियन फ़ंक्शंस के लिए <math>f</math> हैं। उदाहरण के लिए, डी-वें पंक्ति और एस-वें कॉलम में प्रविष्टि 3, 6 है, <math>D(f) = O(\operatorname{s}(f)^{6 + o(1)})</math> सभी के लिए <math>f</math>, और <math>g</math> ऐसा है, कि <math>D(g) = \Omega(\operatorname{s}(g)^{3 - o(1)})</math> वहाँ फ़ंक्शन उपलब्ध है।
 == यह भी देखें ==
-* तुलना क्रम
+* कम्पैरिज़न क्रम
-* निर्णय वृक्ष
+* डिसीजन ट्री
 * आंडेरा-कार्प-रोसेनबर्ग अनुमान
-*न्यूनतम फैले हुए वृक्ष#निर्णय वृक्ष
+*न्यूनतम फैले हुए ट्री#डिसीजन ट्री
 ==संदर्भ==
@@ Line 152: / Line 154: @@
 {{DEFAULTSORT:Decision Tree Model}}
-श्रेणी:कम्प्यूटेशनल जटिलता सिद्धांत
-श्रेणी:गणना के मॉडल
-श्रेणी:निर्णय वृक्ष
+श्रेणी:कम्प्यूटेशनल कॉम्पलेक्सिटी सिद्धांत
+श्रेणी:कम्प्यूटेशन के मॉडल
+श्रेणी:डिसीजन ट्री
-[[Category: Machine Translated Page]]
+[[Category:CS1 English-language sources (en)]]
-[[Category:Created On 25/07/2023]]
+[[Category:CS1 maint]]
+[[Category:Created On 25/07/2023|Decision Tree Model]]
+[[Category:Lua-based templates|Decision Tree Model]]
+[[Category:Machine Translated Page|Decision Tree Model]]
+[[Category:Pages with script errors|Decision Tree Model]]
+[[Category:Short description with empty Wikidata description|Decision Tree Model]]
+[[Category:Templates Vigyan Ready|Decision Tree Model]]
+[[Category:Templates that add a tracking category|Decision Tree Model]]
+[[Category:Templates that generate short descriptions|Decision Tree Model]]
+[[Category:Templates using TemplateData|Decision Tree Model]]

Anonymous

Search

डिसीजन ट्री मॉडल: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 09:42, 23 August 2023

Contents

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

रैखिक और बीजगणितीय डिसीजन ट्री