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

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

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

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

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

छंटाई के लिए पेड़ों और निचली सीमाओं की तुलना करें

सॉर्टिंग और अन्य समान समस्याओं के लिए एल्गोरिदम को समझने के लिए अक्सर निर्णय वृक्षों का उपयोग किया जाता है; यह सबसे पहले फोर्ड और जॉनसन द्वारा किया गया था।^[1] उदाहरण के लिए, कई सॉर्टिंग एल्गोरिदम तुलनात्मक सॉर्ट हैं, जिसका अर्थ है कि वे केवल इनपुट अनुक्रम के बारे में जानकारी प्राप्त करते हैं $x_{1},x_{2},\ldots ,x_{n}$ स्थानीय तुलनाओं के माध्यम से: परीक्षण करें कि क्या $x_{i}<x_{j}$ , $x_{i}=x_{j}$ , या $x_{i}>x_{j}$ . यह मानते हुए कि क्रमबद्ध की जाने वाली सभी वस्तुएँ विशिष्ट और तुलनीय हैं, इसे हाँ-या-नहीं प्रश्न के रूप में दोहराया जा सकता है: है $x_{i}>x_{j}$ ?

इन एल्गोरिदम को बाइनरी निर्णय पेड़ों के रूप में तैयार किया जा सकता है, जहां प्रश्न तुलना हैं: एक आंतरिक नोड एक प्रश्न से मेल खाता है, और नोड के बच्चे अगली क्वेरी के अनुरूप होते हैं जब प्रश्न का उत्तर हां या नहीं होता है। लीफ नोड्स के लिए, आउटपुट क्रमपरिवर्तन से मेल खाता है $\pi$ यह बताता है कि आइटमों की पूरी तरह से ऑर्डर की गई सूची से इनपुट अनुक्रम को कैसे खंगाला गया था। (इस क्रमपरिवर्तन का उलटा, $\pi ^{-1}$ , इनपुट अनुक्रम को पुनः क्रमित करें।) कोई यह दिखा सकता है कि तुलना प्रकार का उपयोग अवश्य करना चाहिए $\Omega (n\log(n))$ एक सरल तर्क के माध्यम से तुलना: एक एल्गोरिदम के सही होने के लिए, इसे हर संभव क्रमपरिवर्तन को आउटपुट करने में सक्षम होना चाहिए $n$ तत्व; अन्यथा, एल्गोरिदम इनपुट के रूप में उस विशेष क्रमपरिवर्तन के लिए विफल हो जाएगा। इसलिए, इसके संगत निर्णय वृक्ष में कम से कम उतने ही पत्ते होने चाहिए जितने क्रमपरिवर्तन हैं: $n!$ पत्तियाँ। कम से कम कोई बाइनरी ट्री $n!$ पत्तियों में कम से कम गहराई तो होती है $\log _{2}(n!)=\Omega (n\log _{2}(n))$ , इसलिए यह तुलनात्मक सॉर्टिंग एल्गोरिदम के रन टाइम पर निचली सीमा है। इस मामले में, इस समय की जटिलता वाले कई तुलना-सॉर्टिंग एल्गोरिदम का अस्तित्व, जैसे मर्ज़ सॉर्ट और ढेर बनाएं और छांटें, दर्शाता है कि सीमा तंग है।^[2]^: 91

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

अन्य निर्णय वृक्ष निचली सीमाओं का उपयोग यह करता है कि क्वेरी एक तुलना है। उदाहरण के लिए, सबसे छोटी संख्या ज्ञात करने के लिए केवल तुलनाओं का उपयोग करने के कार्य पर विचार करें $n$ नंबर. सबसे छोटी संख्या निर्धारित करने से पहले, सबसे छोटी संख्या को छोड़कर प्रत्येक संख्या को कम से कम एक तुलना में हारना होगा (बड़ी से तुलना करें)। तो, इसमें कम से कम समय लगता है $n-1$ न्यूनतम खोजने के लिए तुलना। (यहां सूचना-सैद्धांतिक तर्क केवल निम्न सीमा देता है $\log(n)$ .) एक समान तर्क ऑर्डर आँकड़ों की गणना के लिए सामान्य निचली सीमा के लिए काम करता है।^[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$ ऐसा है कि $x_{i}=x_{j}$ ) गहराई के बीजगणितीय निर्णय वृक्ष की आवश्यकता है $\Omega (n\log(n))$ .^[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}$ (अर्थात्, सीमाबद्ध दोतरफा त्रुटि के साथ)। $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 के साथ (अर्थात् गणना करता है $f$ बिल्कुल)। $Q_{2}(f)$ और $Q_{E}(f)$ इन्हें आमतौर पर क्वांटम क्वेरी जटिलताओं के रूप में जाना जाता है, क्योंकि क्वांटम निर्णय वृक्ष की प्रत्यक्ष परिभाषा शास्त्रीय मामले की तुलना में अधिक जटिल है। यादृच्छिक मामले के समान, हम परिभाषित करते हैं $Q_{0}(f)$ और $Q_{1}(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]

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

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

इन सभी प्रकार की क्वेरी जटिलताएँ बहुपद से संबंधित हैं। ब्लम और इम्पाग्लियाज़ो,^[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]इसलिए, कुछ लोगों के लिए संवेदनशीलता अनुमान को दोबारा दर्शाया जा सकता है $c$ , $bs(f)=O(s(f)^{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]

Anonymous

Search

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

Namespaces

More

Page actions

Contents

छंटाई के लिए पेड़ों और निचली सीमाओं की तुलना करें

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