डिसीजन ट्री मॉडल: 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 2: / Line 2: @@
 [[कम्प्यूटेशनल जटिलता|कम्प्यूटेशनल कॉम्पलेक्सिटी]] में '''[[निर्णय वृक्ष|डिसीजन ट्री]] मॉडल''' [[गणना का मॉडल|कम्प्यूटेशन का मॉडल]] है जिसमें एल्गोरिथ्म को मूल रूप से डिसीजन ट्री माना जाता है, अर्थात, प्रश्नों या परीक्षणों का क्रम जो अनुकूली विधि से किया जाता है, इसलिए पिछले परीक्षणों के परिणाम अगले किए गए परीक्षणों को प्रभावित कर सकते हैं।
-सामान्यतः, इन परीक्षणों में परिणामों की छोटी संख्या होती है (जैसे यैस-नो प्रश्न) और इन्हें जल्दी से निष्पादित किया जा सकता है (जैसे, यूनिट कम्प्यूटेशनल कॉस्ट के साथ), इसलिए डिसीजन ट्री मॉडल में एल्गोरिदम की सबसे वर्स्ट केस टाइम कॉम्पलेक्सिटी से मेल खाती है संबंधित डिसीजन ट्री की डेप्थ डिसीजन ट्री मॉडल में किसी समस्या या एल्गोरिदम की कम्प्यूटेशनल कॉम्पलेक्सिटी की इस धारणा को इसकी डिसीजन ट्री कॉम्पलेक्सिटी या क्वेरी कॉम्पलेक्सिटी कहा जाता है।
+सामान्यतः, इन परीक्षणों में परिणामों की छोटी संख्या होती है (जैसे यैस-नो प्रश्न) और इन्हें जल्दी से निष्पादित किया जा सकता है (जैसे, यूनिट कम्प्यूटेशनल कॉस्ट के साथ), इसलिए डिसीजन ट्री मॉडल में कलन विधि की सबसे वर्स्ट केस टाइम कॉम्पलेक्सिटी से मेल खाती है संबंधित डिसीजन ट्री की डेप्थ डिसीजन ट्री मॉडल में किसी समस्या या कलन विधि की कम्प्यूटेशनल कॉम्पलेक्सिटी की इस धारणा को इसकी डिसीजन ट्री कॉम्पलेक्सिटी या क्वेरी कॉम्पलेक्सिटी कहा जाता है।
-डिसीजन ट्री मॉडल कम्प्यूटेशनल समस्याओं और एल्गोरिदम के कुछ वर्गों के लिए कॉम्पलेक्सिटी सिद्धांत के लिए निम्न बाउंड स्थापित करने में सहायक होते हैं। कम्प्यूटेशनल मॉडल और क्वेरी एल्गोरिदम के सॉर्ट के आधार पर डिसीजन ट्री मॉडल के कई प्रकार प्रस्तुत किए गए हैं।
+डिसीजन ट्री मॉडल कम्प्यूटेशनल प्रॉब्लम्स और कलन विधि के कुछ क्लासेस के लिए कॉम्पलेक्सिटी सिद्धांत के लिए निम्न बाउंड स्थापित करने में सहायक होते हैं। कम्प्यूटेशनल मॉडल और क्वेरी कलन विधि के सॉर्ट के आधार पर डिसीजन ट्री मॉडल के कई प्रकार प्रस्तुत किए गए हैं।
-उदाहरण के लिए, डिसीजन ट्री तर्क का उपयोग यह दिखाने के लिए किया जाता है, कि कम्पैरिज़न सॉर्ट <math>n</math> आइटम अवश्य लेने होता है, <math>n\log(n)</math> कम्पैरिज़न की जाती है। कम्पैरिज़न सॉर्टों के लिए, क्वेरी दो आइटम्स की कम्पैरिज़न है, a, b दो परिणामों के साथ (यह मानते हुए कि कोई आइटम समान नहीं हैं), या तो a<nowiki><b या a>b, इस मॉडल में कम्पैरिज़न सॉर्टों को डिसीजन ट्री के रूप में व्यक्त किया जा सकता है, क्योंकि ऐसे सॉर्टिंग एल्गोरिदम मात्र इस सॉर्ट के प्रश्नों को निष्पादित करते हैं।</nowiki>
+उदाहरण के लिए, डिसीजन ट्री तर्क का उपयोग यह दिखाने के लिए किया जाता है, कि कम्पैरिज़न सॉर्ट <math>n</math> आइटम अवश्य होता है, और <math>n\log(n)</math> कम्पैरिज़न की जाती है। कम्पैरिज़न सॉर्टों के लिए, क्वेरी दो आइटम्स की कम्पैरिज़न है, a, b दो परिणामों के साथ (यह मानते हुए कि कोई आइटम समान नहीं हैं), या तो a<nowiki><b या a>b, इस मॉडल में कम्पैरिज़न सॉर्टों को डिसीजन ट्री के रूप में व्यक्त किया जा सकता है, क्योंकि ऐसे सॉर्टिंग कलन विधि मात्र इस सॉर्ट के प्रश्नों को निष्पादित करते हैं।</nowiki>
 ==सॉर्टिंग के लिए ट्री और लोवर बाउंड का कम्पैरिज़न करें==
-सॉर्टिंग और अन्य समान समस्याओं के लिए तथा एल्गोरिदम को समझने के लिए अधिकांशतः डिसीजन ट्री का उपयोग किया जाता है, यह सबसे पहले फोर्ड और जॉनसन द्वारा किया गया है।<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</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}}
@@ Line 24: / Line 24: @@
 ==रैखिक और बीजगणितीय डिसीजन ट्री==
-रैखिक डिसीजन ट्री उपरोक्त कम्पैरिज़न डिसीजन ट्री को वास्तविक सदिश लेने वाले अभिकलन कार्यों के लिए सामान्यीकृत करते हैं, <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 - x_j</math>क्योंकि बीच की कम्पैरिज़न <math>x_i</math> और <math>x_j</math> रैखिक फ़ंक्शन से मेल खाता है, इसकी परिभाषा से, रैखिक डिसीजन ट्री मात्र कार्य निर्दिष्ट कर सकते हैं, <math>f</math> जिसके फ़ाइबर का निर्माण आधे-स्थानों के संघों और प्रतिच्छेदनों को लेकर किया जा सकता है।
 बीजगणितीय डिसीजन ट्री रैखिक डिसीजन ट्री का सामान्यीकरण है, जो परीक्षण कार्यों को डिग्री के बहुपद होने की अनुमति देते हैं। <math>d</math> ज्यामितीय रूप से, समष्टि को अर्ध-बीजगणितीय समूह (हाइपरसमतल का सामान्यीकरण) में विभाजित किया गया है।
@@ Line 34: / Line 34: @@
 ===डेटर्मीनिस्टिक डिसीजन ट्री===
-यदि डिसीजन ट्री का आउटपुट है, <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>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>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> कम से कम संभावना के साथ 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>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>
@@ Line 159: / Line 159: @@
 श्रेणी:डिसीजन ट्री
+[[Category:CS1 English-language sources (en)]]
-[[Category: Machine Translated Page]]
+[[Category:CS1 maint]]
-[[Category:Created On 25/07/2023]]
+[[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

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

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