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

Revision as of 16:08, 6 August 2023

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

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

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

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

छंटाई के लिए वृक्ष और निम्न परिबद्धओं की तुलना करें

सॉर्टिंग और अन्य समान समस्याओं के लिए एल्गोरिदम को समझने के लिए अधिकांशतः निर्णय वृक्षों का उपयोग किया जाता है, यह सबसे पहले फोर्ड और जॉनसन द्वारा किया गया है।^[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 ^{-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)$ संभव है; ऐसी समस्या का पहला उदाहरण Deutsch और Jozsa द्वारा खोजा गया था।

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

बूलियन फ़ंक्शन के लिए $f:\{0,1\}^{n}\to \{0,1\}$ , की संवेदनशीलता $f$ को अधिकतम संवेदनशीलता के रूप में परिभाषित किया गया है, $f$ सब से ऊपर $x$ , जहां की संवेदनशीलता $f$ पर $x$ एकल-बिट परिवर्तित की संख्या है, $x$ जो $f(x)$ का मान बदलता है, संवेदनशीलता बूलियन फ़ंक्शंस के विश्लेषण से कुल प्रभाव की धारणा से संबंधित है, $x$ जो सभी पर औसत संवेदनशीलता के समतुल्य है।

संवेदनशीलता अनुमान वह अनुमान है, कि संवेदनशीलता बहुपद रूप से क्वेरी सम्मिश्रता से संबंधित है, अर्थात् घातांक विद्यमान है, $c,c'$ ऐसा कि, सभी के लिए $f$ , $D(f)=O(s(f)^{c})$ और $s(f)=O(D(f)^{c'})$ है, $s(f)\leq D(f)$ कोई एक साधारण तर्क के माध्यम से यह दिखा सकता है, इसलिए अनुमान विशेष रूप से संवेदनशीलता के लिए निम्न सीमा खोजने के बारे में चिंतित है। चूंकि पहले चर्चा की गई सभी सम्मिश्रता माप बहुपद से संबंधित हैं, इसलिए उपयुक्त प्रकार की सम्मिश्रता माप प्रासंगिक नहीं है। चूंकि, इसे सामान्यतः ब्लॉक संवेदनशीलता के साथ संवेदनशीलता से संबंधित प्रश्न के रूप में व्यक्त किया जाता है।

की ब्लॉक संवेदनशीलता $f$ , निरूपित $bs(f)$ , की अधिकतम ब्लॉक संवेदनशीलता के रूप में परिभाषित किया गया है, $f$ सब से ऊपर $x$ की ब्लॉक संवेदनशीलता $f$ पर $x$ अधिकतम संख्या है, $t$ असंयुक्त उपसमुच्चय का $S_{1},\ldots ,S_{t}\subset [n]$ ऐसा कि, किसी भी उपसमुच्चय के लिए $S_{i}$ , के बिट्स फ़्लिप करना $x$ तदनुसार $S_{i}$ का मान बदल देता है $f(x)$ .^[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: @@
 {{Use American English|date=January 2019}}
-[[कम्प्यूटेशनल जटिलता]] में [[निर्णय वृक्ष]] मॉडल [[गणना का मॉडल]] है जिसमें एक एल्गोरिथ्म को मूल रूप से एक निर्णय वृक्ष माना जाता है, अर्थात, प्रश्नों या परीक्षणों का एक क्रम जो अनुकूली तरीके से किया जाता है, इसलिए पिछले परीक्षणों के परिणाम अगले किए गए परीक्षणों को प्रभावित कर सकते हैं।
+[[कम्प्यूटेशनल जटिलता|अभिकलनात्मक सम्मिश्रता]] में [[निर्णय वृक्ष]] मॉडल [[गणना का मॉडल]] है जिसमें एक एल्गोरिथ्म को मूल रूप से एक निर्णय वृक्ष माना जाता है, अर्थात, प्रश्नों या परीक्षणों का एक क्रम जो अनुकूली विधि से किया जाता है, इसलिए पिछले परीक्षणों के परिणाम अगले किए गए परीक्षणों को प्रभावित कर सकते हैं।
-आम तौर पर, इन परीक्षणों में परिणामों की एक छोटी संख्या होती है (जैसे हां-नहीं प्रश्न) और इन्हें जल्दी से निष्पादित किया जा सकता है (जैसे, इकाई कम्प्यूटेशनल लागत के साथ), इसलिए निर्णय वृक्ष मॉडल में एल्गोरिदम की सबसे खराब स्थिति समय जटिलता से मेल खाती है संबंधित निर्णय वृक्ष की गहराई निर्णय वृक्ष मॉडल में किसी समस्या या एल्गोरिदम की कम्प्यूटेशनल जटिलता की इस धारणा को इसकी निर्णय वृक्ष जटिलता या क्वेरी जटिलता कहा जाता है।
+सामान्यतः, इन परीक्षणों में परिणामों की एक छोटी संख्या होती है (जैसे हां-नहीं प्रश्न) और इन्हें जल्दी से निष्पादित किया जा सकता है (जैसे, इकाई अभिकलनात्मक लागत के साथ), इसलिए निर्णय वृक्ष मॉडल में एल्गोरिदम की सबसे खराब स्थिति समय सम्मिश्रता से मेल खाती है संबंधित निर्णय वृक्ष की गहराई निर्णय वृक्ष मॉडल में किसी समस्या या एल्गोरिदम की अभिकलनात्मक सम्मिश्रता की इस धारणा को इसकी निर्णय वृक्ष सम्मिश्रता या क्वेरी सम्मिश्रता कहा जाता है।
-निर्णय वृक्ष मॉडल कम्प्यूटेशनल समस्याओं और एल्गोरिदम के कुछ वर्गों के लिए जटिलता सिद्धांत के लिए निम्न परिबद्ध स्थापित करने में सहायक होते हैं। कम्प्यूटेशनल मॉडल और क्वेरी एल्गोरिदम के प्रकार के आधार पर निर्णय वृक्ष मॉडल के कई प्रकार पेश किए गए हैं।
+निर्णय वृक्ष मॉडल अभिकलनात्मक समस्याओं और एल्गोरिदम के कुछ वर्गों के लिए सम्मिश्रता सिद्धांत के लिए निम्न परिबद्ध स्थापित करने में सहायक होते हैं। अभिकलनात्मक मॉडल और क्वेरी एल्गोरिदम के प्रकार के आधार पर निर्णय वृक्ष मॉडल के कई प्रकार प्रस्तुत किए गए हैं।
-उदाहरण के लिए, एक निर्णय वृक्ष तर्क का उपयोग यह दिखाने के लिए किया जाता है, कि तुलनात्मक प्रकार <math>n</math> आइटम अवश्य लेने होता है, <math>n\log(n)</math> तुलना की जाती है। तुलना प्रकारों के लिए, एक क्वेरी दो वस्तुओं की तुलना है, ए, बी दो परिणामों के साथ (यह मानते हुए कि कोई आइटम समान नहीं हैं), या तो ए<बी या ए>बी. इस मॉडल में तुलना प्रकारों को निर्णय वृक्ष के रूप में व्यक्त किया जा सकता है, क्योंकि ऐसे सॉर्टिंग एल्गोरिदम केवल इस प्रकार के प्रश्नों को निष्पादित करते हैं।
+उदाहरण के लिए, एक निर्णय वृक्ष तर्क का उपयोग यह दिखाने के लिए किया जाता है, कि तुलनात्मक प्रकार <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^{-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> एन नंबर है, जो सबसे छोटी संख्या निर्धारित करने से पहले, सबसे छोटी संख्या को छोड़कर प्रत्येक संख्या को कम से कम एक तुलना में "हारना" (बड़ी तुलना करना) होता है। तो, इसमें कम से कम समय लगता है, न्यूनतम ज्ञात करने के लिए n-1 तुलना होती है। यहां सूचना-सैद्धांतिक तर्क मात्र निम्न परिबद्ध देता है, एक समान तर्क ऑर्डर आँकड़ों की गणना के लिए सामान्य निम्न परिबद्ध के लिए काम करता है।<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 - x_j</math>क्योंकि बीच की तुलना <math>x_i</math> और <math>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>\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>
-== बूलियन निर्णय वृक्ष जटिलताएँ ==
+== बूलियन निर्णय वृक्ष सम्मिश्रता ==
-बूलियन निर्णय वृक्षों के लिए, कार्य एन-बिट [[बूलियन फ़ंक्शन]] के मान की गणना करना है, <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>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>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>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>
-==बूलियन फ़ंक्शन जटिलता उपायों के बीच संबंध==
+==बूलियन फ़ंक्शन सम्मिश्रता माध्यमों के बीच संबंध==
-यह परिभाषाओं से तुरंत पता चलता है कि <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>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>-बिट बूलियन फ़ंक्शन है, विपरीत दिशा में सर्वोत्तम ऊपरी सीमा ढूँढना क्वेरी सम्मिश्रता के क्षेत्र में एक प्रमुख लक्ष्य है।
-इन सभी प्रकार की क्वेरी जटिलताएँ बहुपद से संबंधित हैं। ब्लम और इम्पाग्लियाज़ो,<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"/>
+इन सभी प्रकार की क्वेरी सम्मिश्रताएँ बहुपद से संबंधित हैं। ब्लम और इम्पाग्लियाज़ो,<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> संभव है; ऐसी समस्या का पहला उदाहरण Deutsch और Jozsa द्वारा खोजा गया था।
+यह ध्यान रखना महत्वपूर्ण है, कि ये बहुपद संबंध मात्र कुल बूलियन कार्यों के लिए मान्य हैं। आंशिक बूलियन फ़ंक्शंस के लिए, <math>\{0,1\}^n</math> जिसमें एक डोमेन का सबसमूह होता है, कि बीच एक घातांकीय पृथक्करण <math>Q_0(f)</math> और <math>D(f)</math> संभव है; ऐसी समस्या का पहला उदाहरण Deutsch और Jozsa द्वारा खोजा गया था।
 === संवेदनशीलता अनुमान ===
-बूलियन फ़ंक्शन के लिए <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>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>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>
-जुलाई 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 123: / Line 123: @@
 | 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 156: / Line 156: @@
 {{DEFAULTSORT:Decision Tree Model}}
-श्रेणी:कम्प्यूटेशनल जटिलता सिद्धांत
+श्रेणी:अभिकलनात्मक सम्मिश्रता सिद्धांत
 श्रेणी:गणना के मॉडल
 श्रेणी:निर्णय वृक्ष

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 16:08, 6 August 2023

Contents

छंटाई के लिए वृक्ष और निम्न परिबद्धओं की तुलना करें

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