सर्किट जटिलता: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{Short description|Model of computational complexity}}
{{Short description|Model of computational complexity}}


[[सैद्धांतिक कंप्यूटर विज्ञान]] में, परिपथ जटिलता [[कम्प्यूटेशनल जटिलता सिद्धांत]] की शाखा है जिसमें बूलियन कार्यों को [[बूलियन सर्किट|बूलियन परिपथ]] के आकार या गहराई के अनुसार वर्गीकृत किया जाता है जो उनकी गणना करते हैं। संबंधित धारणा [[पुनरावर्ती भाषा]] की परिपथ जटिलता है जो मशीन है जो सदैव परिपथ के समान परिवार द्वारा रुकती है <math>C_{1},C_{2},\ldots</math> (नीचे देखें)।
[[सैद्धांतिक कंप्यूटर विज्ञान]] में, परिपथ जटिलता [[कम्प्यूटेशनल जटिलता सिद्धांत]] की शाखा है जिसमें बूलियन कार्यों को [[बूलियन सर्किट|बूलियन परिपथ]] के आकार या गहराई के अनुसार वर्गीकृत किया जाता है जो उनकी गणना करते हैं। संबंधित धारणा [[पुनरावर्ती भाषा]] की परिपथ जटिलता है जो मशीन है जो सदैव परिपथ के समान वर्ग द्वारा रुकती है <math>C_{1},C_{2},\ldots</math> (नीचे देखें)।


स्पष्ट बूलियन कार्यों की गणना करने वाले बूलियन परिपथ के आकार पर निचली सीमा प्रदान करना जटिलता वर्गों को अलग करने का लोकप्रिय विधि है। उदाहरण के लिए, P/पॉली या इसका महत्व P/पॉली परिपथ क्लास P/पॉली में बहुपद आकार के परिपथ द्वारा गणना योग्य बूलियन फ़ंक्शन होते हैं। यह सिद्ध करना <math>\mathsf{NP}\not\subseteq \mathsf{P/poly}</math> [[पी (जटिलता)]] और [[एनपी (जटिलता)]] को अलग करेगा (नीचे देखें)।
स्पष्ट बूलियन कार्यों की गणना करने वाले बूलियन परिपथ के आकार पर निचली सीमा प्रदान करना जटिलता वर्गों को अलग करने का लोकप्रिय विधि है। उदाहरण के लिए, P/पॉली या इसका महत्व P/पॉली परिपथ क्लास P/पॉली में बहुपद आकार के परिपथ द्वारा गणना योग्य बूलियन फ़ंक्शन होते हैं। यह सिद्ध करना <math>\mathsf{NP}\not\subseteq \mathsf{P/poly}</math> [[पी (जटिलता)]] और [[एनपी (जटिलता)]] को अलग करेगा (नीचे देखें)।


बूलियन सर्किट के संदर्भ में परिभाषित जटिलता वर्गों में एसी0, एसी, टीसी0, एनसी1, एनसी और पी/पॉली सम्मिलित हैं।
बूलियन सर्किट के संदर्भ में परिभाषित जटिलता वर्गों में एसी0, एसी, टीसी0, एनसी1, एनसी और पी/पॉली सम्मिलित हैं।


== आकार और गहराई ==
== आकार और गहराई ==
n इनपुट बिट्स के साथ बूलियन परिपथ एक निर्देशित अचक्रीय ग्राफ है जिसमें प्रत्येक नोड (सामान्यतः इस संदर्भ में गेट्स कहा जाता है) या तो [[इन-डिग्री]] 0 का इनपुट नोड होता है जिसे किसी द्वारा लेबल किया जाता है। <math>n</math> इनपुट बिट्स, एंड गेट, औरगेट या नॉटगेट। इनमें से गेट को आउटपुट गेट के रूप में नामित किया गया है। ऐसा परिपथ स्वाभाविक रूप से इसके फ़ंक्शन की गणना करता है <math>n</math> आदानों। परिपथ का आकार इसमें सम्मिलित फाटकों की संख्या है और इसकी गहराई इनपुट गेट से आउटपुट गेट तक पथ की अधिकतम लंबाई है।
n इनपुट बिट्स के साथ बूलियन परिपथ एक निर्देशित अचक्रीय ग्राफ है जिसमें प्रत्येक नोड (सामान्यतः इस संदर्भ में गेट्स कहा जाता है) या तो [[इन-डिग्री]] 0 का इनपुट नोड होता है जिसे किसी द्वारा लेबल किया जाता है। <math>n</math> इनपुट बिट्स, एंड गेट, औरगेट या नॉटगेट। इनमें से गेट को आउटपुट गेट के रूप में नामित किया गया है। ऐसा परिपथ स्वाभाविक रूप से इसके फ़ंक्शन की गणना करता है <math>n</math> आदानों। परिपथ का आकार इसमें सम्मिलित फाटकों की संख्या है और इसकी गहराई इनपुट गेट से आउटपुट गेट तक पथ की अधिकतम लंबाई है।


परिपथ जटिलता की दो प्रमुख धारणाएँ हैं<ref name="Sipser_1997"/> <math>f</math> बूलियन फलन की परिपथ-आकार की जटिलता <math>f</math> किसी भी परिपथ कंप्यूटिंग का न्यूनतम आकार है <math>f</math>. बूलियन फ़ंक्शन की परिपथ-गहराई जटिलता <math>f</math> किसी भी परिपथ कंप्यूटिंग की न्यूनतम गहराई है .
परिपथ जटिलता की दो प्रमुख धारणाएँ हैं<ref name="Sipser_1997"/> <math>f</math> बूलियन फलन की परिपथ-आकार की जटिलता <math>f</math> किसी भी परिपथ कंप्यूटिंग का न्यूनतम आकार है <math>f</math>. बूलियन फ़ंक्शन की परिपथ-गहराई जटिलता <math>f</math> किसी भी परिपथ कंप्यूटिंग की न्यूनतम गहराई है .


ये धारणाएं सामान्यीकृत होती हैं जब कोई किसी भाषा की परिपथ जटिलता पर विचार करता है जिसमें अलग-अलग बिट लंबाई वाले तार होते हैं, विशेष रूप से अनंत [[औपचारिक भाषा]]एं। यद्यपि, बूलियन परिपथ केवल निश्चित संख्या में इनपुट बिट्स की अनुमति देते हैं। इस प्रकार, कोई एकल बूलियन परिपथ ऐसी भाषा तय करने में सक्षम नहीं है। इस संभावना को ध्यान में रखते हुए, परिपथ के परिवारों पर विचार किया जाता है <math>C_{1},C_{2},\ldots</math> जहां प्रत्येक <math>C_{n}</math> आकार के इनपुट स्वीकार करता है <math>n</math>. प्रत्येक परिपथ परिवार  परिपथ द्वारा स्वाभाविक रूप से भाषा उत्पन्न करेगा <math>C_{n}</math> आउटपुटिंग <math>1</math> जब लंबाई <math>n</math> स्ट्रिंग परिवार का सदस्य है, और <math>0</math> अन्यथा। हम कहते हैं कि परिपथ का परिवार न्यूनतम आकार का होता है यदि कोई अन्य परिवार नहीं है जो किसी भी आकार के इनपुट पर निर्णय लेता है, <math>n</math>, से छोटे आकार के परिपथ के साथ <math>C_n</math> (क्रमशः गहराई न्यूनतम परिवारों के लिए)। इस प्रकार, पुनरावर्ती भाषा | गैर-पुनरावर्ती भाषाओं के लिए भी परिपथ जटिलता सार्थक है। समान परिवार की धारणा परिपथ जटिलता के वेरिएंट को पुनरावर्ती भाषाओं के एल्गोरिथ्म आधारित जटिलता उपायों से संबंधित होने में सक्षम बनाती है। चूंकि, दी गई भाषाओं को तय करने के लिए किसी भी परिपथ परिवार को कितना जटिल होना चाहिए, इस पर निचली सीमाएं खोजने में गैर-समान संस्करण सहायक होता है।
ये धारणाएं सामान्यीकृत होती हैं जब कोई किसी भाषा की परिपथ जटिलता पर विचार करता है जिसमें अलग-अलग बिट लंबाई वाले तार होते हैं, विशेष रूप से अनंत [[औपचारिक भाषा]]एं। यद्यपि, बूलियन परिपथ केवल निश्चित संख्या में इनपुट बिट्स की अनुमति देते हैं। इस प्रकार, कोई एकल बूलियन परिपथ ऐसी भाषा तय करने में सक्षम नहीं है। इस संभावना को ध्यान में रखते हुए, परिपथ के वर्गों पर विचार किया जाता है <math>C_{1},C_{2},\ldots</math> जहां प्रत्येक <math>C_{n}</math> आकार के इनपुट स्वीकार करता है <math>n</math>. प्रत्येक परिपथ वर्ग परिपथ द्वारा स्वाभाविक रूप से भाषा उत्पन्न करेगा <math>C_{n}</math> आउटपुटिंग <math>1</math> जब लंबाई <math>n</math> स्ट्रिंग वर्ग का सदस्य है, और <math>0</math> अन्यथा। हम कहते हैं कि परिपथ का वर्ग न्यूनतम आकार का होता है यदि कोई अन्य वर्ग नहीं है जो किसी भी आकार के इनपुट पर निर्णय लेता है, <math>n</math>, से छोटे आकार के परिपथ के साथ <math>C_n</math> (क्रमशः गहराई न्यूनतम वर्गों के लिए)। इस प्रकार, पुनरावर्ती भाषा | गैर-पुनरावर्ती भाषाओं के लिए भी परिपथ जटिलता सार्थक है। समान वर्ग की धारणा परिपथ जटिलता के वेरिएंट को पुनरावर्ती भाषाओं के एल्गोरिथ्म आधारित जटिलता उपायों से संबंधित होने में सक्षम बनाती है। चूंकि, दी गई भाषाओं को तय करने के लिए किसी भी परिपथ वर्ग को कितना जटिल होना चाहिए, इस पर निचली सीमाएं खोजने में गैर-समान संस्करण सहायक होता है।


इसलिए, औपचारिक भाषा की परिपथ-आकार की जटिलता <math>A</math> समारोह के रूप में परिभाषित किया गया है <math>t:\mathbb{N}\to\mathbb{N}</math>, जो इनपुट की थोड़ी लंबाई से संबंधित है, <math>n</math>, न्यूनतम परिपथ के परिपथ-आकार की जटिलता के लिए <math>C_{n}</math> यह तय करता है कि उस लंबाई के इनपुट अंदर हैं या नहीं <math>A</math>. परिपथ-डेप्थ जटिलता को इसी तरह परिभाषित किया गया है।
इसलिए, औपचारिक भाषा की परिपथ-आकार की जटिलता <math>A</math> समारोह के रूप में परिभाषित किया गया है <math>t:\mathbb{N}\to\mathbb{N}</math>, जो इनपुट की थोड़ी लंबाई से संबंधित है, <math>n</math>, न्यूनतम परिपथ के परिपथ-आकार की जटिलता के लिए <math>C_{n}</math> यह तय करता है कि उस लंबाई के इनपुट अंदर हैं या नहीं <math>A</math>. परिपथ-डेप्थ जटिलता को इसी तरह परिभाषित किया गया है।


== एकरूपता ==
== एकरूपता ==
बूलियन परिपथ तथाकथित गैर-समान सार मशीन के प्रमुख उदाहरणों में से हैं, इस अर्थ में कि अलग-अलग लंबाई के इनपुट को अलग-अलग परिपथ द्वारा संसाधित किया जाता है, इसके विपरीत [[ट्यूरिंग मशीन]] जैसे समान मॉडल के विपरीत, जहां सभी संभव के लिए ही कम्प्यूटेशनल डिवाइस का उपयोग किया जाता है। इनपुट लंबाई। व्यक्तिगत [[कम्प्यूटेशनल समस्या]] इस प्रकार बूलियन परिपथ के विशेष परिवार से जुड़ी हुई है <math>C_1, C_2, \dots </math> जहां प्रत्येक <math>C_n</math> n बिट्स का परिपथ हैंडलिंग इनपुट है। इन परिवारों पर अधिकांशतः एकरूपता की शर्त लगाई जाती है, जिसके लिए कुछ संभावित [[कम्प्यूटेशनल संसाधन]] | संसाधन-बद्ध ट्यूरिंग मशीन के अस्तित्व की आवश्यकता होती है, जो इनपुट एन पर, व्यक्तिगत परिपथ का विवरण तैयार करती है। <math>C_n</math>. जब इस ट्यूरिंग मशीन का रनिंग टाइम बहुपद n में होता है, तो परिपथ परिवार को P-वर्दी कहा जाता है। [[DLOGTIME]]- एकरूपता की कठोर आवश्यकता एसी जैसे उथले-गहराई वाले परिपथ-वर्गों के अध्ययन में विशेष रुचि रखती है<sup>0</sup> या टीसी<sup>0</उप>। जब कोई संसाधन सीमा निर्दिष्ट नहीं की जाती है, तो भाषा पुनरावर्ती होती है (अर्थात, ट्यूरिंग मशीन द्वारा तय की जा सकती है) यदि और केवल यदि भाषा बूलियन परिपथ के समान परिवार द्वारा तय की जाती है।
बूलियन परिपथ तथाकथित गैर-समान सार मशीन के प्रमुख उदाहरणों में से हैं, इस अर्थ में कि अलग-अलग लंबाई के इनपुट को अलग-अलग परिपथ द्वारा संसाधित किया जाता है, इसके विपरीत [[ट्यूरिंग मशीन]] जैसे समान मॉडल के विपरीत, जहां सभी संभव के लिए ही कम्प्यूटेशनल डिवाइस का उपयोग किया जाता है। इनपुट लंबाई। व्यक्तिगत [[कम्प्यूटेशनल समस्या]] इस प्रकार बूलियन परिपथ के विशेष वर्ग से जुड़ी हुई है <math>C_1, C_2, \dots </math> जहां प्रत्येक <math>C_n</math> n बिट्स का परिपथ हैंडलिंग इनपुट है। इन वर्गों पर अधिकांशतः एकरूपता की शर्त लगाई जाती है, जिसके लिए कुछ संभावित [[कम्प्यूटेशनल संसाधन]] | संसाधन-बद्ध ट्यूरिंग मशीन के अस्तित्व की आवश्यकता होती है, जो इनपुट एन पर, व्यक्तिगत परिपथ का विवरण तैयार करती है। <math>C_n</math>. जब इस ट्यूरिंग मशीन का रनिंग टाइम बहुपद n में होता है, तो परिपथ वर्ग को P-वर्दी कहा जाता है। [[DLOGTIME]]- एकरूपता की कठोर आवश्यकता एसी जैसे उथले-गहराई वाले परिपथ-वर्गों के अध्ययन में विशेष रुचि रखती है<sup>0</sup> या टीसी<sup>0</उप>जब कोई संसाधन सीमा निर्दिष्ट नहीं की जाती है, तो एक भाषा पुनरावर्ती होती है (यानी, ट्यूरिंग मशीन द्वारा तय की जा सकती है) अगर और केवल अगर भाषा बूलियन सर्किट के एक समान वर्ग द्वारा तय की जाती है।


=== बहुपद-समय की वर्दी ===
=== बहुपद-समय की वर्दी ===
बूलियन परिपथ का परिवार <math>\{C_n:n \in \mathbb{N}\}</math> यदि [[नियतात्मक ट्यूरिंग मशीन]] M उपस्थ है, तो बहुपद-समय एकसमान है, जैसे कि
बूलियन परिपथ का वर्ग <math>\{C_n:n \in \mathbb{N}\}</math> यदि [[नियतात्मक ट्यूरिंग मशीन]] M उपस्थ है, तो बहुपद-समय एकसमान है, जैसे कि
* एम बहुपद समय में चलता है
* एम बहुपद समय में चलता है
* सभी के लिए <math>n \in \mathbb{N}</math>, M का विवरण आउटपुट करता है <math>C_n</math> इनपुट पर <math>1^n</math>
* सभी के लिए <math>n \in \mathbb{N}</math>, M का विवरण आउटपुट करता है <math>C_n</math> इनपुट पर <math>1^n</math>
Line 26: Line 26:


=== लॉगस्पेस वर्दी ===
=== लॉगस्पेस वर्दी ===
बूलियन परिपथ का परिवार <math>\{C_n:n \in \mathbb{N}\}</math> यदि नियतात्मक ट्यूरिंग मशीन M उपस्थ है, तो लॉगस्पेस एकसमान है, जैसे कि
बूलियन परिपथ का वर्ग <math>\{C_n:n \in \mathbb{N}\}</math> यदि नियतात्मक ट्यूरिंग मशीन M उपस्थ है, तो लॉगस्पेस एकसमान है, जैसे कि
* एम लॉगरिदमिक स्पेस में चलता है
* एम लॉगरिदमिक स्पेस में चलता है
* सभी के लिए <math>n \in \mathbb{N}</math>, M का विवरण आउटपुट करता है <math>C_n</math> इनपुट पर <math>1^n</math>
* सभी के लिए <math>n \in \mathbb{N}</math>, M का विवरण आउटपुट करता है <math>C_n</math> इनपुट पर <math>1^n</math>
Line 32: Line 32:


== इतिहास ==
== इतिहास ==
1949 में परिपथ जटिलता [[क्लाउड शैनन]] के पास वापस जाती है,<ref name="Shannon_1949"/>जिन्होंने सिद्ध किया कि n चरों पर लगभग सभी बूलियन कार्यों के लिए आकार Θ(2) के परिपथों की आवश्यकता होती है<sup>एन</sup>/n). इस तथ्य के अतिरिक्त, जटिलता सिद्धांतवादी अब तक किसी भी स्पष्ट कार्य के लिए सुपरलीनियर लोअर बाउंड सिद्ध करने में असमर्थ रहे हैं।
1949 में परिपथ जटिलता [[क्लाउड शैनन]] के पास वापस जाती है,<ref name="Shannon_1949"/>जिन्होंने सिद्ध किया कि n चरों पर लगभग सभी बूलियन कार्यों के लिए आकार Θ(2) के परिपथों की आवश्यकता होती है<sup>एन</sup>/n). इस तथ्य के अतिरिक्त, जटिलता सिद्धांतवादी अब तक किसी भी स्पष्ट कार्य के लिए सुपरलीनियर लोअर बाउंड सिद्ध करने में असमर्थ रहे हैं।


उपयोग किए गए परिपथ के परिवार पर कुछ प्रतिबंधों के अनुसार अधिबहुपद निचली सीमाएं सिद्ध हुई हैं। पहला कार्य जिसके लिए अधिबहुपद परिपथ निचली सीमाएँ दिखाई गई थीं, समता फ़ंक्शन था, जो इसके इनपुट बिट्स मॉड्यूलो 2 के योग की गणना करता है। तथ्य यह है कि समानता AC0|AC में समाहित नहीं है।<sup>0</sup> पहली बार 1983 में अजताई द्वारा स्वतंत्र रूप से स्थापित किया गया था<ref name="Ajtai_1983"/><ref name="Ajtai-Komlós-Szemerédi_1983"/>और 1984 में फुर्स्ट, सक्से और सिप्सर द्वारा।<ref name="Furst-Saxe-Sipser_1984"/> बाद में 1987 में जोहान हास्ताद|हस्ताद द्वारा सुधार किया गया<ref name="Håstad_1987"/> स्थापित किया गया है कि समता फ़ंक्शन की गणना करने वाले निरंतर-गहराई वाले परिपथ के किसी भी परिवार को घातीय आकार की आवश्यकता होती है। रज़बोरोव के परिणाम का विस्तार,<ref name="Razborov_1985"/>1987 में स्मोलेंस्की<ref name="Smolensky_1987"/> सिद्ध हुआ कि यह सच है तथापि परिपथ गेट्स के साथ संवर्धित हो, इसके इनपुट बिट्स मॉडुलो कुछ विषम प्राइम पी के योग की गणना करता है।
उपयोग किए गए परिपथ के वर्ग पर कुछ प्रतिबंधों के अनुसार अधिबहुपद निचली सीमाएं सिद्ध हुई हैं। पहला कार्य जिसके लिए अधिबहुपद परिपथ निचली सीमाएँ दिखाई गई थीं, समता फ़ंक्शन था, जो इसके इनपुट बिट्स मॉड्यूलो 2 के योग की गणना करता है। तथ्य यह है कि समानता AC0|AC में समाहित नहीं है।<sup>0</sup> पहली बार 1983 में अजताई द्वारा स्वतंत्र रूप से स्थापित किया गया था<ref name="Ajtai_1983"/><ref name="Ajtai-Komlós-Szemerédi_1983"/>और 1984 में फुर्स्ट, सक्से और सिप्सर द्वारा।<ref name="Furst-Saxe-Sipser_1984"/> बाद में 1987 में जोहान हास्ताद|हस्ताद द्वारा सुधार किया गया<ref name="Håstad_1987"/> स्थापित किया गया है कि समता फ़ंक्शन की गणना करने वाले निरंतर-गहराई वाले परिपथ के किसी भी वर्ग को घातीय आकार की आवश्यकता होती है। रज़बोरोव के परिणाम का विस्तार,<ref name="Razborov_1985"/>1987 में स्मोलेंस्की<ref name="Smolensky_1987"/> सिद्ध हुआ कि यह सच है तथापि परिपथ गेट्स के साथ संवर्धित हो, इसके इनपुट बिट्स मॉडुलो कुछ विषम प्राइम पी के योग की गणना करता है।


क्लिक समस्या | के-क्लिक समस्या यह तय करने के लिए है कि क्या n शिखर पर दिए गए ग्राफ में आकार के आकार का चक्कर है। स्थिरांक n और k के किसी विशेष विकल्प के लिए, ग्राफ़ को बाइनरी में एन्कोड किया जा सकता है <math>{n \choose 2}</math> बिट्स, जो प्रत्येक संभावित किनारे के लिए इंगित करता है कि यह उपस्थ है या नहीं। फिर के-क्लिक समस्या को समारोह के रूप में औपचारिक रूप दिया जाता है <math>f_k:\{0,1\}^{{n \choose 2}}\to\{0,1\}</math> ऐसा है कि <math>f_k</math> आउटपुट 1 यदि और केवल तभी जब स्ट्रिंग द्वारा एन्कोड किए गए ग्राफ़ में आकार k का समूह होता है। कार्यों का यह परिवार मोनोटोन है और इसकी गणना परिपथ के परिवार द्वारा की जा सकती है, किन्तु यह दिखाया गया है कि इसकी गणना मोनोटोन परिपथ के बहुपद-आकार के परिवार द्वारा नहीं की जा सकती है (अर्थात, एंड और और गेट वाले परिपथ किन्तु बिना निषेध के)। 1985 में [[अलेक्जेंडर रज़बोरोव]] का मूल परिणाम<ref name="Razborov_1985"/> बाद में 1987 में अलोन और बोपना द्वारा घातीय-आकार के निचले हिस्से में सुधार किया गया।<ref name="Alon-Boppana_1987"/> 2008 में, रॉसमैन<ref name="Rossman_2008"/> ने दिखाया कि एंड, औरऔर नॉटगेट्स वाले स्थिर-गहराई वाले परिपथों के लिए आकार की आवश्यकता होती है <math>\Omega(n^{k/4})</math> औसत स्थितियोंे की जटिलता में भी के-क्लिक समस्या को हल करने के लिए। इसके अतिरिक्त, आकार का परिपथ है <math>n^{k/4+O(1)}</math> जो गणना करता है <math>f_k</math>.
क्लिक समस्या | के-क्लिक समस्या यह तय करने के लिए है कि क्या n शिखर पर दिए गए ग्राफ में आकार के आकार का चक्कर है। स्थिरांक n और k के किसी विशेष विकल्प के लिए, ग्राफ़ को बाइनरी में एन्कोड किया जा सकता है <math>{n \choose 2}</math> बिट्स, जो प्रत्येक संभावित किनारे के लिए इंगित करता है कि यह उपस्थ है या नहीं। फिर के-क्लिक समस्या को समारोह के रूप में औपचारिक रूप दिया जाता है <math>f_k:\{0,1\}^{{n \choose 2}}\to\{0,1\}</math> ऐसा है कि <math>f_k</math> आउटपुट 1 यदि और केवल तभी जब स्ट्रिंग द्वारा एन्कोड किए गए ग्राफ़ में आकार k का समूह होता है। कार्यों का यह वर्ग मोनोटोन है और इसकी गणना परिपथ के वर्ग द्वारा की जा सकती है, किन्तु यह दिखाया गया है कि इसकी गणना मोनोटोन परिपथ के बहुपद-आकार के वर्ग द्वारा नहीं की जा सकती है (अर्थात, एंड और और गेट वाले परिपथ किन्तु बिना निषेध के)। 1985 में [[अलेक्जेंडर रज़बोरोव]] का मूल परिणाम<ref name="Razborov_1985"/> बाद में 1987 में अलोन और बोपना द्वारा घातीय-आकार के निचले हिस्से में सुधार किया गया।<ref name="Alon-Boppana_1987"/> 2008 में, रॉसमैन<ref name="Rossman_2008"/> ने दिखाया कि एंड, औरऔर नॉटगेट्स वाले स्थिर-गहराई वाले परिपथों के लिए आकार की आवश्यकता होती है <math>\Omega(n^{k/4})</math> औसत स्थितियोंे की जटिलता में भी के-क्लिक समस्या को हल करने के लिए। इसके अतिरिक्त, आकार का परिपथ है <math>n^{k/4+O(1)}</math> जो गणना करता है <math>f_k</math>.


1999 में, [[घाव एक बार|घाव बार]] और [[पियरे मैकेंजी]] ने बाद में दिखाया कि मोनोटोन एनसी पदानुक्रम अनंत है।<ref name="Raz-McKenzie_1999"/>
1999 में, [[घाव एक बार|घाव बार]] और [[पियरे मैकेंजी]] ने बाद में दिखाया कि मोनोटोन एनसी पदानुक्रम अनंत है।<ref name="Raz-McKenzie_1999"/>
Line 47: Line 47:
* समता असमान AC0|AC में नहीं है<sup>0</sup>, अजताई द्वारा 1983 में सिद्ध किया गया<ref name="Ajtai_1983"/><ref name="Ajtai-Komlós-Szemerédi_1983"/> साथ ही 1984 में फुर्स्ट, सक्से और सिप्सर द्वारा।<ref name="Furst-Saxe-Sipser_1984"/>* यूनिफ़ॉर्म TC0|TC<sup>0</sup> [[पीपी (जटिलता)]] में सख्ती से समाहित है, जिसे एलेंडर ने सिद्ध किया है।<ref name="Allender_1997"/> वर्ग S2P (जटिलता)|S{{su|p=P|b=2}}, पीपी<ref group="nb" name="NB1"/> और [[एमए (जटिलता)]]/1<ref name="Santhanam_2007"/> ( सलाह के साथ एमए) आकार में नहीं हैं ('' एन<sup>k</sup>) किसी भी स्थिर k के लिए।
* समता असमान AC0|AC में नहीं है<sup>0</sup>, अजताई द्वारा 1983 में सिद्ध किया गया<ref name="Ajtai_1983"/><ref name="Ajtai-Komlós-Szemerédi_1983"/> साथ ही 1984 में फुर्स्ट, सक्से और सिप्सर द्वारा।<ref name="Furst-Saxe-Sipser_1984"/>* यूनिफ़ॉर्म TC0|TC<sup>0</sup> [[पीपी (जटिलता)]] में सख्ती से समाहित है, जिसे एलेंडर ने सिद्ध किया है।<ref name="Allender_1997"/> वर्ग S2P (जटिलता)|S{{su|p=P|b=2}}, पीपी<ref group="nb" name="NB1"/> और [[एमए (जटिलता)]]/1<ref name="Santhanam_2007"/> ( सलाह के साथ एमए) आकार में नहीं हैं ('' एन<sup>k</sup>) किसी भी स्थिर k के लिए।
* जबकि यह संदेह है कि गैर-वर्दी वर्ग ACC0 में बहुमत का कार्य सम्मिलित नहीं है, यह केवल 2010 में [[रयान विलियम्स (कंप्यूटर वैज्ञानिक)]] ने सिद्ध किया था {{nowrap|<math>\mathsf{NEXP} \not \subseteq \mathsf{ACC}^0</math>.<ref name="Williams_2011"/>}}
* जबकि यह संदेह है कि गैर-वर्दी वर्ग ACC0 में बहुमत का कार्य सम्मिलित नहीं है, यह केवल 2010 में [[रयान विलियम्स (कंप्यूटर वैज्ञानिक)]] ने सिद्ध किया था {{nowrap|<math>\mathsf{NEXP} \not \subseteq \mathsf{ACC}^0</math>.<ref name="Williams_2011"/>}}
यह खुला है कि क्या नेक्स्पटाइम के ​​पास असमान टीसी है<sup>0</sup> परिपथ।
यह खुला है कि क्या नेक्स्पटाइम के ​​पास असमान टीसी है<sup>0</sup> परिपथ।


परिपथ लोअर बाउंड्स के सबूत [[derandomization|डेरनडोमाईजेशन]] से दृढ़ता से जुड़े हुए हैं। सबूत है कि <math>\mathsf{P} = \mathsf{BPP}</math> इसका मतलब यह होगा कि या तो <math>\mathsf{NEXP} \not \subseteq \mathsf{P/poly}</math> या उस स्थायी की गणना बहुपद आकार और बहुपद डिग्री के गैर-समान अंकगणितीय परिपथ (बहुपद) द्वारा नहीं की जा सकती।<ref name="Kabanets-Impagliazzo_2004"/>
परिपथ लोअर बाउंड्स के सबूत [[derandomization|डेरनडोमाईजेशन]] से दृढ़ता से जुड़े हुए हैं। सबूत है कि <math>\mathsf{P} = \mathsf{BPP}</math> इसका मतलब यह होगा कि या तो <math>\mathsf{NEXP} \not \subseteq \mathsf{P/poly}</math> या उस स्थायी की गणना बहुपद आकार और बहुपद डिग्री के गैर-समान अंकगणितीय परिपथ (बहुपद) द्वारा नहीं की जा सकती।<ref name="Kabanets-Impagliazzo_2004"/>


1997 में, रज़बोरोव और रुडिच ने दिखाया कि स्पष्ट बूलियन कार्यों के लिए कई ज्ञात परिपथ निचली सीमाएं संबंधित परिपथ वर्ग के विरुद्ध तथाकथित [[प्राकृतिक प्रमाण]] के अस्तित्व का संकेत देती हैं।<ref name="Razborov-Rudich_1997"/> दूसरी ओर, पी/पॉली के खिलाफ उपयोगी प्राकृतिक गुण शक्तिशाली छद्म यादृच्छिक जनरेटर को तोड़ देंगे। इसे अधिकांशतः शक्तिशाली परिपथ निचली सीमा सिद्ध करने के लिए प्राकृतिक सबूत बाधा के रूप में व्याख्या की जाती है। 2016 में, कारमोसिनो, इम्पैग्लियाज़ो, कबनेट्स और कोलोकोलोवा ने सिद्ध कर दिया कि कुशल शिक्षण एल्गोरिदम के निर्माण के लिए प्राकृतिक गुणों का भी उपयोग किया जा सकता है।<ref name="Carmosino-Impagliazzo-Kabanets-Kolokolova_2016"/>
1997 में, रज़बोरोव और रुडिच ने दिखाया कि स्पष्ट बूलियन कार्यों के लिए कई ज्ञात परिपथ निचली सीमाएं संबंधित परिपथ वर्ग के विरुद्ध तथाकथित [[प्राकृतिक प्रमाण]] के अस्तित्व का संकेत देती हैं।<ref name="Razborov-Rudich_1997"/> दूसरी ओर, पी/पॉली के खिलाफ उपयोगी प्राकृतिक गुण शक्तिशाली छद्म यादृच्छिक जनरेटर को तोड़ देंगे। इसे अधिकांशतः शक्तिशाली परिपथ निचली सीमा सिद्ध करने के लिए प्राकृतिक सबूत बाधा के रूप में व्याख्या की जाती है। 2016 में, कारमोसिनो, इम्पैग्लियाज़ो, कबनेट्स और कोलोकोलोवा ने सिद्ध कर दिया कि कुशल शिक्षण एल्गोरिदम के निर्माण के लिए प्राकृतिक गुणों का भी उपयोग किया जा सकता है।<ref name="Carmosino-Impagliazzo-Kabanets-Kolokolova_2016"/>




== जटिलता वर्ग ==
== जटिलता वर्ग ==
कई परिपथ जटिलता वर्गों को वर्ग पदानुक्रमों के संदर्भ में परिभाषित किया गया है। प्रत्येक गैर-ऋणात्मक पूर्णांक i के लिए, वर्ग NC (जटिलता)|NC होता है<sup>i</sup>, जिसमें गहराई के बहुपद-आकार के परिपथ सम्मिलित हैं <math>O(\log^i(n))</math>, बाउंडेड फैन-इन एंड, और, और नॉट गेट्स का उपयोग करना। इन सभी वर्गों की संघ एनसी चर्चा का विषय है। असीमित फैन-इन गेट्स पर विचार करके, कक्षाएं एसी (जटिलता) | एसी<sup>i</sup> और AC (जो NC के बराबर है) की रचना की जा सकती है। गेट्स के विभिन्न समुच्चयों की अनुमति देकर ही आकार और गहराई प्रतिबंधों के साथ कई अन्य परिपथ जटिलता वर्गों का निर्माण किया जा सकता है।
कई परिपथ जटिलता वर्गों को वर्ग पदानुक्रमों के संदर्भ में परिभाषित किया गया है। प्रत्येक गैर-ऋणात्मक पूर्णांक i के लिए, वर्ग NC (जटिलता)|NC होता है<sup>i</sup>, जिसमें गहराई के बहुपद-आकार के परिपथ सम्मिलित हैं <math>O(\log^i(n))</math>, बाउंडेड फैन-इन एंड, और, और नॉट गेट्स का उपयोग करना। इन सभी वर्गों की संघ एनसी चर्चा का विषय है। असीमित फैन-इन गेट्स पर विचार करके, कक्षाएं एसी (जटिलता) | एसी<sup>i</sup> और AC (जो NC के बराबर है) की रचना की जा सकती है। गेट्स के विभिन्न समुच्चयों की अनुमति देकर ही आकार और गहराई प्रतिबंधों के साथ कई अन्य परिपथ जटिलता वर्गों का निर्माण किया जा सकता है।


== समय जटिलता से संबंध ==
== समय जटिलता से संबंध ==
यदि कोई निश्चित भाषा, <math>A</math>, कॉम्प्लेक्सिटी क्लास | टाइम-कॉम्प्लेक्सिटी क्लास से संबंधित है <math>\text{TIME}(t(n))</math> किसी समारोह के लिए <math>t:\mathbb{N}\to\mathbb{N}</math>, तब <math>A</math> परिपथ जटिलता है <math>\mathcal{O}(t(n) \log t(n))</math>. यदि भाषा को स्वीकार करने वाली ट्यूरिंग मशीन [[ट्यूरिंग मशीन समकक्ष]] है (जिसका अर्थ है कि यह इनपुट की परवाह किए बिना समान मेमोरी सेल को पढ़ती और लिखती है), तो <math>A</math> परिपथ जटिलता है <math>\mathcal{O}(t(n))</math>.<ref>{{Citation|first=Nicholas|last=Pippenger|authorlink=Nick Pippenger|first2=Michael J.|last2=Fischer|authorlink2=Michael J. Fischer|title=Relations Among Complexity Measures|journal=[[Journal of the ACM]]|year=1979|volume=26|issue=3|pages=361–381|doi=10.1145/322123.322138}}
यदि कोई निश्चित भाषा, <math>A</math>, कॉम्प्लेक्सिटी क्लास | टाइम-कॉम्प्लेक्सिटी क्लास से संबंधित है <math>\text{TIME}(t(n))</math> किसी समारोह के लिए <math>t:\mathbb{N}\to\mathbb{N}</math>, तब <math>A</math> परिपथ जटिलता है <math>\mathcal{O}(t(n) \log t(n))</math>. यदि भाषा को स्वीकार करने वाली ट्यूरिंग मशीन [[ट्यूरिंग मशीन समकक्ष]] है (जिसका अर्थ है कि यह इनपुट की परवाह किए बिना समान मेमोरी सेल को पढ़ती और लिखती है), तो <math>A</math> परिपथ जटिलता है <math>\mathcal{O}(t(n))</math>.<ref>{{Citation|first=Nicholas|last=Pippenger|authorlink=Nick Pippenger|first2=Michael J.|last2=Fischer|authorlink2=Michael J. Fischer|title=Relations Among Complexity Measures|journal=[[Journal of the ACM]]|year=1979|volume=26|issue=3|pages=361–381|doi=10.1145/322123.322138}}
</ref>
</ref>


Revision as of 11:44, 24 February 2023

सैद्धांतिक कंप्यूटर विज्ञान में, परिपथ जटिलता कम्प्यूटेशनल जटिलता सिद्धांत की शाखा है जिसमें बूलियन कार्यों को बूलियन परिपथ के आकार या गहराई के अनुसार वर्गीकृत किया जाता है जो उनकी गणना करते हैं। संबंधित धारणा पुनरावर्ती भाषा की परिपथ जटिलता है जो मशीन है जो सदैव परिपथ के समान वर्ग द्वारा रुकती है (नीचे देखें)।

स्पष्ट बूलियन कार्यों की गणना करने वाले बूलियन परिपथ के आकार पर निचली सीमा प्रदान करना जटिलता वर्गों को अलग करने का लोकप्रिय विधि है। उदाहरण के लिए, P/पॉली या इसका महत्व P/पॉली परिपथ क्लास P/पॉली में बहुपद आकार के परिपथ द्वारा गणना योग्य बूलियन फ़ंक्शन होते हैं। यह सिद्ध करना पी (जटिलता) और एनपी (जटिलता) को अलग करेगा (नीचे देखें)।

बूलियन सर्किट के संदर्भ में परिभाषित जटिलता वर्गों में एसी0, एसी, टीसी0, एनसी1, एनसी और पी/पॉली सम्मिलित हैं।

आकार और गहराई

n इनपुट बिट्स के साथ बूलियन परिपथ एक निर्देशित अचक्रीय ग्राफ है जिसमें प्रत्येक नोड (सामान्यतः इस संदर्भ में गेट्स कहा जाता है) या तो इन-डिग्री 0 का इनपुट नोड होता है जिसे किसी द्वारा लेबल किया जाता है। इनपुट बिट्स, एंड गेट, औरगेट या नॉटगेट। इनमें से गेट को आउटपुट गेट के रूप में नामित किया गया है। ऐसा परिपथ स्वाभाविक रूप से इसके फ़ंक्शन की गणना करता है आदानों। परिपथ का आकार इसमें सम्मिलित फाटकों की संख्या है और इसकी गहराई इनपुट गेट से आउटपुट गेट तक पथ की अधिकतम लंबाई है।

परिपथ जटिलता की दो प्रमुख धारणाएँ हैं[1] बूलियन फलन की परिपथ-आकार की जटिलता किसी भी परिपथ कंप्यूटिंग का न्यूनतम आकार है . बूलियन फ़ंक्शन की परिपथ-गहराई जटिलता किसी भी परिपथ कंप्यूटिंग की न्यूनतम गहराई है .

ये धारणाएं सामान्यीकृत होती हैं जब कोई किसी भाषा की परिपथ जटिलता पर विचार करता है जिसमें अलग-अलग बिट लंबाई वाले तार होते हैं, विशेष रूप से अनंत औपचारिक भाषाएं। यद्यपि, बूलियन परिपथ केवल निश्चित संख्या में इनपुट बिट्स की अनुमति देते हैं। इस प्रकार, कोई एकल बूलियन परिपथ ऐसी भाषा तय करने में सक्षम नहीं है। इस संभावना को ध्यान में रखते हुए, परिपथ के वर्गों पर विचार किया जाता है जहां प्रत्येक आकार के इनपुट स्वीकार करता है . प्रत्येक परिपथ वर्ग परिपथ द्वारा स्वाभाविक रूप से भाषा उत्पन्न करेगा आउटपुटिंग जब लंबाई <