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

Revision as of 15:11, 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]

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

Best-known separations for complexity measures as of October 2020^[update]^[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 4: / Line 4: @@
 [[कम्प्यूटेशनल जटिलता]] में [[निर्णय वृक्ष]] मॉडल [[गणना का मॉडल]] है जिसमें एक एल्गोरिथ्म को मूल रूप से एक निर्णय वृक्ष माना जाता है, अर्थात, प्रश्नों या परीक्षणों का एक क्रम जो अनुकूली तरीके से किया जाता है, इसलिए पिछले परीक्षणों के परिणाम अगले किए गए परीक्षणों को प्रभावित कर सकते हैं।
-आम तौर पर, इन परीक्षणों में परिणामों की एक छोटी संख्या होती है (जैसे हां-नहीं प्रश्न) और इन्हें जल्दी से निष्पादित किया जा सकता है (जैसे, इकाई कम्प्यूटेशनल लागत के साथ), इसलिए निर्णय वृक्ष मॉडल में एल्गोरिदम की सबसे खराब स्थिति समय जटिलता से मेल खाती है संबंधित निर्णय वृक्ष की गहराई. निर्णय वृक्ष मॉडल में किसी समस्या या एल्गोरिदम की कम्प्यूटेशनल जटिलता की इस धारणा को इसकी निर्णय वृक्ष जटिलता या क्वेरी जटिलता कहा जाता है।
+आम तौर पर, इन परीक्षणों में परिणामों की एक छोटी संख्या होती है (जैसे हां-नहीं प्रश्न) और इन्हें जल्दी से निष्पादित किया जा सकता है (जैसे, इकाई कम्प्यूटेशनल लागत के साथ), इसलिए निर्णय वृक्ष मॉडल में एल्गोरिदम की सबसे खराब स्थिति समय जटिलता से मेल खाती है संबंधित निर्णय वृक्ष की गहराई निर्णय वृक्ष मॉडल में किसी समस्या या एल्गोरिदम की कम्प्यूटेशनल जटिलता की इस धारणा को इसकी निर्णय वृक्ष जटिलता या क्वेरी जटिलता कहा जाता है।
-निर्णय वृक्ष मॉडल कम्प्यूटेशनल समस्याओं और एल्गोरिदम के कुछ वर्गों के लिए जटिलता सिद्धांत के लिए निचली सीमा स्थापित करने में सहायक होते हैं। कम्प्यूटेशनल मॉडल और क्वेरी एल्गोरिदम के प्रकार के आधार पर निर्णय वृक्ष मॉडल के कई प्रकार पेश किए गए हैं।
+निर्णय वृक्ष मॉडल कम्प्यूटेशनल समस्याओं और एल्गोरिदम के कुछ वर्गों के लिए जटिलता सिद्धांत के लिए निम्न परिबद्ध स्थापित करने में सहायक होते हैं। कम्प्यूटेशनल मॉडल और क्वेरी एल्गोरिदम के प्रकार के आधार पर निर्णय वृक्ष मॉडल के कई प्रकार पेश किए गए हैं।
 उदाहरण के लिए, एक निर्णय वृक्ष तर्क का उपयोग यह दिखाने के लिए किया जाता है, कि तुलनात्मक प्रकार <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>
@@ Line 16: / Line 16: @@
 उदाहरण के लिए, कई सॉर्टिंग एल्गोरिदम तुलनात्मक सॉर्ट हैं, जिसका अर्थ है, कि वे केवल इनपुट अनुक्रम के बारे में जानकारी प्राप्त करते हैं, <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> नंबर. सबसे छोटी संख्या निर्धारित करने से पहले, सबसे छोटी संख्या को छोड़कर प्रत्येक संख्या को कम से कम एक तुलना में हारना होगा (बड़ी से तुलना करें)। तो, इसमें कम से कम समय लगता है <math>n-1</math> न्यूनतम खोजने के लिए तुलना। (यहां सूचना-सैद्धांतिक तर्क केवल निम्न सीमा देता है <math>\log(n)</math>.) एक समान तर्क ऑर्डर आँकड़ों की गणना के लिए सामान्य निचली सीमा के लिए काम करता है।<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</math> और <math>x_j</math> रैखिक फलन से मेल खाता है <math>x_i - 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>x_i = x_j</math>) गहराई के बीजगणितीय निर्णय वृक्ष की आवश्यकता है <math>\Omega(n\log(n))</math>.<ref>{{Cite journal|last=Ben-Or|first=Michael|date=1983-12-01|title=बीजगणितीय संगणना वृक्षों के लिए निचली सीमाएँ|url=https://doi.org/10.1145/800061.808735|journal=Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing|series=STOC '83|location=New York, NY, USA|publisher=Association for Computing Machinery|pages=80–86|doi=10.1145/800061.808735|isbn=978-0-89791-099-6|s2cid=1499957|doi-access=free}}</ref> इसे पहली बार डोबकिन और लिप्टन द्वारा रैखिक निर्णय मॉडल के लिए दिखाया गया था।<ref>{{Cite journal|last1=Dobkin|first1=David|last2=Lipton|first2=Richard J.|date=1976-06-01|title=बहुआयामी खोज समस्याएँ|url=https://epubs.siam.org/doi/10.1137/0205015|journal=SIAM Journal on Computing|volume=5|issue=2|pages=181–186|doi=10.1137/0205015|issn=0097-5397}}</ref> वे यह भी दिखाते हैं <math>n^2</math> नैपसैक समस्या पर रैखिक निर्णय वृक्षों के लिए निचली सीमा, स्टील और याओ द्वारा बीजगणितीय निर्णय वृक्षों के लिए सामान्यीकृत।<ref>{{Cite journal|last1=Michael Steele|first1=J|last2=Yao|first2=Andrew C|date=1982-03-01|title=बीजगणितीय निर्णय वृक्षों के लिए निचली सीमाएँ|url=https://dx.doi.org/10.1016%2F0196-6774%2882%2990002-5|journal=Journal of Algorithms|language=en|volume=3|issue=1|pages=1–8|doi=10.1016/0196-6774(82)90002-5|issn=0196-6774}}</ref>
+राबिन<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>R_2(f)</math>को सबसे कम गहराई वाले यादृच्छिक निर्णय वृक्ष की जटिलता के रूप में परिभाषित किया गया है जिसका परिणाम है <math>f(x)</math> कम से कम संभावना के साथ <math>2/3</math> सभी के लिए <math>x\in \{0,1\}^n</math> (अर्थात्, सीमाबद्ध दोतरफा त्रुटि के साथ)।<math>R_2(f)</math>[[मोंटे कार्लो एल्गोरिथ्म]] को यादृच्छिक निर्णय-वृक्ष जटिलता के रूप में जाना जाता है, क्योंकि परिणाम को दो-तरफा त्रुटि के साथ गलत होने की अनुमति है। [[ लास वेगास एल्गोरिथ्म |लास वेगास एल्गोरिथ्म]] निर्णय-वृक्ष जटिलता<math>R_0(f)</math>निर्णय वृक्ष की ''अपेक्षित'' गहराई को मापता है जो सही होना चाहिए (यानी, शून्य-त्रुटि है)। एक तरफा बाउंडेड-एरर संस्करण भी है जिसे द्वारा दर्शाया गया है<math>R_1(f)</math>.
+यादृच्छिक निर्णय वृक्ष को परिभाषित करने का एक तरीका वृक्ष में अतिरिक्त नोड्स जोड़ना है, <math>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>f</math> पर <math>x</math> सूचकांकों के सबसे छोटे उपसमुच्चय का आकार है, <math>S \subset [n]</math> ऐसा कि, सभी के लिए <math>y \in \{0,1\}^n</math>, यदि <math>y_i = x_i</math> सभी के लिए <math>i \in S</math>, तब <math>f(y) = f(x)</math> है, की प्रमाणपत्र जटिलता <math>f</math> सभी की तुलना में <math>x</math> अधिकतम प्रमाणपत्र जटिलता है, अनुरूप धारणा जहां किसी को केवल 2/3 संभावना के साथ सत्यापनकर्ता के सही होने की आवश्यकता होती है, <math>RC(f)</math> उसे दर्शाया गया है।
 ===क्वांटम निर्णय वृक्ष===
-क्वांटम निर्णय वृक्ष जटिलता<math>Q_2(f)</math>सबसे कम गहराई वाले क्वांटम निर्णय वृक्ष की गहराई है जो परिणाम देती है <math>f(x)</math> कम से कम संभावना के साथ <math>2/3</math> सभी के लिए <math>x\in \{0,1\}^n </math>. अन्य मात्रा,<math>Q_E(f)</math>, को परिणाम देने वाले सबसे कम गहराई वाले क्वांटम निर्णय वृक्ष की गहराई के रूप में परिभाषित किया गया है <math>f(x)</math> सभी मामलों में प्रायिकता 1 के साथ (अर्थात् गणना करता है <math>f</math> बिल्कुल)। <math>Q_2(f)</math> और <math>Q_E(f)</math> इन्हें आमतौर पर क्वांटम क्वेरी जटिलताओं के रूप में जाना जाता है, क्योंकि क्वांटम निर्णय वृक्ष की प्रत्यक्ष परिभाषा शास्त्रीय मामले की तुलना में अधिक जटिल है। यादृच्छिक मामले के समान, हम परिभाषित करते हैं <math>Q_0(f)</math> और <math>Q_1(f)</math>.
+क्वांटम निर्णय वृक्ष जटिलता <math>Q_2(f)</math> सबसे कम गहराई वाले क्वांटम निर्णय वृक्ष की गहराई है, जो परिणाम होता है, <math>f(x)</math> कम से कम संभावना के साथ 2 / 3 सभी के लिए <math>x\in \{0,1\}^n </math>, अन्य मात्रा, <math>Q_E(f)</math>, को परिणाम देने वाले सबसे कम गहराई वाले क्वांटम निर्णय वृक्ष की गहराई के रूप में परिभाषित किया गया है, <math>f(x)</math> सभी मामलों में प्रायिकता 1 के साथ (अर्थात गणना करता है � एफ बिल्कुल)। <math>Q_2(f)</math> और <math>Q_E(f)</math> को आमतौर पर क्वांटम क्वेरी जटिलताओं के रूप में जाना जाता है, क्योंकि क्वांटम निर्णय वृक्ष की प्रत्यक्ष परिभाषा शास्त्रीय मामले की तुलना में अधिक जटिल है। यादृच्छिक मामले के समान, हम परिभाषित करते हैं।
-ये धारणाएँ आम तौर पर डिग्री और अनुमानित डिग्री की धारणाओं से बंधी होती हैं। की डिग्री <math>f</math>, निरूपित <math>\deg(f)</math>, किसी भी बहुपद की सबसे छोटी डिग्री है <math>p</math> संतुष्टि देने वाला <math>f(x) = p(x)</math> सभी के लिए <math>x \in \{0,1\}^n</math>. की अनुमानित डिग्री <math>f</math>, निरूपित <math>\widetilde{\deg}(f)</math>, किसी भी बहुपद की सबसे छोटी डिग्री है <math>p</math> संतुष्टि देने वाला <math>p(x) \in [0,1/3]</math> जब कभी भी <math>f(x) = 0</math> और <math>p(x) \in [2/3, 1]</math> जब कभी भी <math>f(x) = 1</math>.
+ये धारणाएँ आम तौर पर डिग्री और अनुमानित डिग्री की धारणाओं से बंधी होती हैं। की डिग्री <math>f</math>, निरूपित <math>\deg(f)</math>, किसी भी बहुपद की सबसे छोटी डिग्री है, <math>p</math> संतोषजनक <math>f(x) = p(x)</math> सभी के लिए <math>x \in \{0,1\}^n</math>, की अनुमानित डिग्री <math>f</math>, निरूपित <math>\widetilde{\deg}(f)</math>, किसी भी बहुपद की सबसे छोटी डिग्री है, <math>p</math> संतोषजनक <math>p(x) \in [0,1/3]</math> जब भी <math>f(x) = 0</math> और <math>p(x) \in [2/3, 1]</math> जब भी <math>f(x) = 1</math>.
+बील्स एट अल. <math>Q_0(f) \geq \deg(f)/2</math> और <math>Q_2(f) \geq \widetilde{\deg}(f)/2</math> उसे स्थापित किया गया है.<ref name="Beals">{{cite journal | last=Beals | first=R. |author2=Buhrman, H. |author3=Cleve, R. |author4=Mosca, M. |author5= de Wolf, R.  | year = 2001 | title= बहुपदों द्वारा क्वांटम निचली सीमाएँ| journal =Journal of the ACM | volume=48 | issue=4 | pages=778–797 | doi=10.1145/502090.502097|arxiv=quant-ph/9802049 | s2cid=1078168 }}</ref>
-बील्स एट अल. उसे स्थापित किया <math>Q_0(f) \geq \deg(f)/2</math> और <math>Q_2(f) \geq \widetilde{\deg}(f)/2</math>.<ref name="Beals">{{cite journal | last=Beals | first=R. |author2=Buhrman, H. |author3=Cleve, R. |author4=Mosca, M. |author5= de Wolf, R.  | year = 2001 | title= बहुपदों द्वारा क्वांटम निचली सीमाएँ| journal =Journal of the ACM | volume=48 | issue=4 | pages=778–797 | doi=10.1145/502090.502097|arxiv=quant-ph/9802049 | s2cid=1078168 }}</ref>
 ==बूलियन फ़ंक्शन जटिलता उपायों के बीच संबंध==
-यह परिभाषाओं से तुरंत पता चलता है कि सभी के लिए <math>n</math>-बिट बूलियन फ़ंक्शन <math>f</math>,<math>Q_2(f) \leq R_2(f) \leq R_1(f) \leq R_0(f) \leq D(f) \leq n</math>, और <math>Q_2(f) \leq Q_0(f) \leq D(f) \leq n</math>. विपरीत दिशा में सर्वोत्तम ऊपरी सीमा ढूँढना क्वेरी जटिलता के क्षेत्र में एक प्रमुख लक्ष्य है।
+यह परिभाषाओं से तुरंत पता चलता है कि <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>f</math>, निरूपित <math>bs(f)</math>, की अधिकतम ब्लॉक संवेदनशीलता के रूप में परिभाषित किया गया है <math>f</math> कुल मिलाकर <math>x</math>. की ब्लॉक संवेदनशीलता <math>f</math> पर <math>x</math> अधिकतम संख्या है <math>t</math> असंयुक्त उपसमुच्चय का <math>S_1, \ldots, S_t \subset [n]</math> ऐसा कि, किसी भी उपसमुच्चय के लिए <math>S_i</math>, के बिट्स फ़्लिप करना <math>x</math> तदनुसार <math>S_i</math> का मान बदल देता है <math>f(x)</math>.<ref name="Nisan"/>
+चूँकि <math>s(f) \leq bs(f)</math> ब्लॉक संवेदनशीलता उपसमुच्चय के अधिक से अधिक संवेदनशीलता प्रतिशत प्रभाव डाले जाते हैं। इसके अलावा, ब्लॉक संवेदनशीलता बहुपद रूप से पहले चर्चा किए गए जटिलता उपायों से संबंधित है, उदाहरण के लिए, <math>bs(f) \leq D(f) = O(bs(f)^4)</math> ब्लॉक-संवेदनशीलता का परिचय विवरण वाले निसान के पेपर में यह दिखाया गया है,<ref name="Nisan"/> इसलिए, <math>bs(f)=O(s(f)^c)</math> कुछ अनुमान के लिए संवेदनशीलता अनुमान <math>c</math> को दोबारा दर्शाया जा सकता है, 1992 में, निसान और सेज़ादी ने यह अनुमान लगाया <math>c = 2</math> पर्याप्त है।<ref name="NisanSzegedy">{{Cite journal|last1=Nisan|first1=Noam|last2=Szegedy|first2=Mario|date=1992-07-01|title=बूलियन की डिग्री पर वास्तविक बहुपद के रूप में कार्य करता है|url=https://doi.org/10.1145/129712.129757|journal=Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing|series=STOC '92|location=Victoria, British Columbia, Canada|publisher=Association for Computing Machinery|pages=462–467|doi=10.1145/129712.129757|isbn=978-0-89791-511-3|s2cid=6919144|doi-access=free}}</ref> यह सख्त होगा, क्योंकि रुबिनस्टीन ने 1995 में संवेदनशीलता और ब्लॉक संवेदनशीलता के बीच एक द्विघात अलगाव दिखाया था।<ref name="Rub95">{{Cite journal|last=Rubinstein|first=David|date=1995-06-01|title=बूलियन फ़ंक्शंस की संवेदनशीलता बनाम ब्लॉक संवेदनशीलता|url=https://doi.org/10.1007/BF01200762|journal=Combinatorica|language=en|volume=15|issue=2|pages=297–299|doi=10.1007/BF01200762|s2cid=41010711|issn=1439-6912}}</ref>
-चूँकि ब्लॉक संवेदनशीलता उपसमुच्चय के अधिक विकल्पों पर अधिकतम प्रभाव डालती है, <math>s(f) \leq bs(f)</math>. इसके अलावा, ब्लॉक संवेदनशीलता बहुपद रूप से पहले चर्चा किए गए जटिलता उपायों से संबंधित है; उदाहरण के लिए, ब्लॉक-संवेदनशीलता का परिचय देने वाले निसान के पेपर ने यह दिखाया <math>bs(f) \leq D(f) = O(bs(f)^4)</math>.<ref name="Nisan"/>इसलिए, कुछ लोगों के लिए संवेदनशीलता अनुमान को दोबारा दर्शाया जा सकता है <math>c</math>, <math>bs(f)=O(s(f)^c)</math>. 1992 में, निसान और सेजेडी ने यह अनुमान लगाया <math>c = 2</math> पर्याप्त.<ref name="NisanSzegedy">{{Cite journal|last1=Nisan|first1=Noam|last2=Szegedy|first2=Mario|date=1992-07-01|title=बूलियन की डिग्री पर वास्तविक बहुपद के रूप में कार्य करता है|url=https://doi.org/10.1145/129712.129757|journal=Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing|series=STOC '92|location=Victoria, British Columbia, Canada|publisher=Association for Computing Machinery|pages=462–467|doi=10.1145/129712.129757|isbn=978-0-89791-511-3|s2cid=6919144|doi-access=free}}</ref> यह कठिन होगा, क्योंकि 1995 में रुबिनस्टीन ने संवेदनशीलता और ब्लॉक संवेदनशीलता के बीच एक द्विघात अलगाव दिखाया था।<ref name="Rub95">{{Cite journal|last=Rubinstein|first=David|date=1995-06-01|title=बूलियन फ़ंक्शंस की संवेदनशीलता बनाम ब्लॉक संवेदनशीलता|url=https://doi.org/10.1007/BF01200762|journal=Combinatorica|language=en|volume=15|issue=2|pages=297–299|doi=10.1007/BF01200762|s2cid=41010711|issn=1439-6912}}</ref>
+जुलाई 2019 में, अनुमान शुरू होने के 27 साल बाद, [[एमोरी विश्वविद्यालय]] के हाओ हुआंग ने संवेदनशीलता अनुमान साबित किया, यह दिखाते हुए <math>bs(f) = O(s(f)^4)</math>,<ref name="Huang">{{Cite journal|last=Huang|first=Hao|date=2019|title=हाइपरक्यूब के प्रेरित उपसमूह और संवेदनशीलता अनुमान का प्रमाण|journal=Annals of Mathematics|volume=190|issue=3|pages=949–955|doi=10.4007/annals.2019.190.3.6|jstor=10.4007/annals.2019.190.3.6|arxiv=1907.00847|s2cid=195767594|issn=0003-486X}}</ref> यह प्रमाण विशेष रूप से संक्षिप्त है, इस कथन को दो पृष्ठों में सिद्ध करता है, जब संवेदनशीलता अनुमान की दिशा में पूर्व प्रगति सीमित थी।<ref>{{Cite web|last=Klarreich|first=Erica|title=दशकों पुराने कंप्यूटर विज्ञान अनुमान को दो पृष्ठों में हल किया गया|url=https://www.quantamagazine.org/mathematician-solves-computer-science-conjecture-in-two-pages-20190725/|access-date=2019-07-26|website=Quanta Magazine}}</ref><ref name="HKP">{{Cite journal|last1=Hatami|first1=Pooya|last2=Kulkarni|first2=Raghav|last3=Pankratov|first3=Denis|date=2011-06-22|title=संवेदनशीलता अनुमान पर भिन्नताएँ|url=http://www.theoryofcomputing.org/articles/gs004|journal=Theory of Computing|volume=1|language=EN|pages=1–27|doi=10.4086/toc.gs.2011.004|s2cid=6918061|issn=1557-2862|doi-access=free}}</ref>
-जुलाई 2019 में, अनुमान शुरू होने के 27 साल बाद, [[एमोरी विश्वविद्यालय]] के हाओ हुआंग (गणितज्ञ) ने संवेदनशीलता अनुमान साबित किया, यह दिखाते हुए <math>bs(f) = O(s(f)^4)</math>.<ref name="Huang">{{Cite journal|last=Huang|first=Hao|date=2019|title=हाइपरक्यूब के प्रेरित उपसमूह और संवेदनशीलता अनुमान का प्रमाण|journal=Annals of Mathematics|volume=190|issue=3|pages=949–955|doi=10.4007/annals.2019.190.3.6|jstor=10.4007/annals.2019.190.3.6|arxiv=1907.00847|s2cid=195767594|issn=0003-486X}}</ref> यह प्रमाण विशेष रूप से संक्षिप्त है, इस कथन को दो पृष्ठों में सिद्ध करता है जब संवेदनशीलता अनुमान की दिशा में पूर्व प्रगति सीमित थी।<ref>{{Cite web|last=Klarreich|first=Erica|title=दशकों पुराने कंप्यूटर विज्ञान अनुमान को दो पृष्ठों में हल किया गया|url=https://www.quantamagazine.org/mathematician-solves-computer-science-conjecture-in-two-pages-20190725/|access-date=2019-07-26|website=Quanta Magazine}}</ref><ref name="HKP">{{Cite journal|last1=Hatami|first1=Pooya|last2=Kulkarni|first2=Raghav|last3=Pankratov|first3=Denis|date=2011-06-22|title=संवेदनशीलता अनुमान पर भिन्नताएँ|url=http://www.theoryofcomputing.org/articles/gs004|journal=Theory of Computing|volume=1|language=EN|pages=1–27|doi=10.4086/toc.gs.2011.004|s2cid=6918061|issn=1557-2862|doi-access=free}}</ref>
 === ज्ञात परिणामों का सारांश{{mw-datatable}} ===
 {| class="wikitable mw-datatable"
@@ Line 121: / Line 125: @@
 यह तालिका बूलियन फ़ंक्शन जटिलता उपायों के बीच अलगाव पर परिणामों का सारांश प्रस्तुत करती है। जटिलता के उपाय, क्रम में, नियतात्मक, शून्य-त्रुटि यादृच्छिक, दो-तरफा-त्रुटि यादृच्छिक, प्रमाणपत्र, यादृच्छिक प्रमाणपत्र, ब्लॉक संवेदनशीलता, संवेदनशीलता, सटीक क्वांटम, डिग्री, क्वांटम और अनुमानित डिग्री जटिलताएं हैं।
-में संख्या <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> वहाँ एक फ़ंक्शन मौजूद है।
 == यह भी देखें ==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 15:11, 6 August 2023

Contents

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

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