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

From Vigyanwiki
(Created page with "{{Short description|Model of computational complexity}} {{Use dmy dates|date=May 2019|cs1-dates=y}} File:Three_input_Boolean_circuit.jpg|thumb|right|300px|उदाहरण...")
 
No edit summary
Line 1: Line 1:
{{Short description|Model of computational complexity}}
{{Short description|Model of computational complexity}}
{{Use dmy dates|date=May 2019|cs1-dates=y}}
[[File:Three_input_Boolean_circuit.jpg|thumb|right|300px|उदाहरण बूलियन सर्किट। <math>\wedge</math> h> नोड AND गेट्स हैं, द <math>\vee</math> नोड [[या द्वार]] हैं, और <math>\neg</math> [[गेट नहीं]] नहीं हैं]][[सैद्धांतिक कंप्यूटर विज्ञान]] में, सर्किट जटिलता [[कम्प्यूटेशनल जटिलता सिद्धांत]] की एक शाखा है जिसमें बूलियन कार्यों को [[बूलियन सर्किट]] के आकार या गहराई के अनुसार वर्गीकृत किया जाता है जो उनकी गणना करते हैं। एक संबंधित धारणा एक [[पुनरावर्ती भाषा]] की सर्किट जटिलता है जो मशीन है जो हमेशा सर्किट के एक समान परिवार द्वारा रुकती है <math>C_{1},C_{2},\ldots</math> (नीचे देखें)।


स्पष्ट बूलियन कार्यों की गणना करने वाले बूलियन सर्किट के आकार पर निचली सीमा प्रदान करना जटिलता वर्गों को अलग करने का एक लोकप्रिय तरीका है। उदाहरण के लिए, P/पॉली#Importance of P/पॉली सर्किट क्लास P/पॉली में बहुपद आकार के सर्किट द्वारा गणना योग्य बूलियन फ़ंक्शन होते हैं। यह साबित करना <math>\mathsf{NP}\not\subseteq \mathsf{P/poly}</math> [[पी (जटिलता)]] और [[एनपी (जटिलता)]] को अलग करेगा (नीचे देखें)।
[[/index.php?title=Special:MathShowImage&hash=b6252c47c600d72b4b0f484c229f580d&mode=mathml|thumb|right|उदाहरण बूलियन सर्किट। <math>\wedge</math> h> नोड AND गेट्स हैं, द <math>\vee</math> नोड [[या द्वार]] हैं, और <math>\neg</math> [[गेट नहीं]] नहीं हैं|link=|alt={\displaystyle \wedge }]][[सैद्धांतिक कंप्यूटर विज्ञान]] में, सर्किट जटिलता [[कम्प्यूटेशनल जटिलता सिद्धांत]] की  शाखा है जिसमें बूलियन कार्यों को [[बूलियन सर्किट]] के आकार या गहराई के अनुसार वर्गीकृत किया जाता है जो उनकी गणना करते हैं।  संबंधित धारणा  [[पुनरावर्ती भाषा]] की सर्किट जटिलता है जो मशीन है जो हमेशा सर्किट के  समान परिवार द्वारा रुकती है <math>C_{1},C_{2},\ldots</math> (नीचे देखें)।
 
स्पष्ट बूलियन कार्यों की गणना करने वाले बूलियन सर्किट के आकार पर निचली सीमा प्रदान करना जटिलता वर्गों को अलग करने का लोकप्रिय तरीका है। उदाहरण के लिए, P/पॉली या Importance of P/पॉली सर्किट क्लास P/पॉली में बहुपद आकार के सर्किट द्वारा गणना योग्य बूलियन फ़ंक्शन होते हैं। यह साबित करना <math>\mathsf{NP}\not\subseteq \mathsf{P/poly}</math> [[पी (जटिलता)]] और [[एनपी (जटिलता)]] को अलग करेगा (नीचे देखें)।


बूलियन सर्किट के संदर्भ में परिभाषित [[जटिलता वर्ग]]ों में AC0|AC शामिल हैं<sup>0</sup>, AC (जटिलता), TC0|TC<sup>0</sup>, NC1 (जटिलता)|NC<sup>1</sup>, एनसी (जटिलता), और पी/पॉली।
बूलियन सर्किट के संदर्भ में परिभाषित [[जटिलता वर्ग]]ों में AC0|AC शामिल हैं<sup>0</sup>, AC (जटिलता), TC0|TC<sup>0</sup>, NC1 (जटिलता)|NC<sup>1</sup>, एनसी (जटिलता), और पी/पॉली।


== आकार और गहराई ==
== आकार और गहराई ==
के साथ एक बूलियन सर्किट <math>n</math> इनपुट [[अंश]]्स एक [[निर्देशित अचक्रीय ग्राफ]] है जिसमें प्रत्येक नोड (आमतौर पर इस संदर्भ में गेट्स कहा जाता है) या तो [[इन-डिग्री]] 0 का इनपुट नोड होता है जिसे किसी एक द्वारा लेबल किया जाता है। <math>n</math> इनपुट बिट्स, AND गेट, OR गेट या NOT गेट। इनमें से एक गेट को आउटपुट गेट के रूप में नामित किया गया है। ऐसा सर्किट स्वाभाविक रूप से इसके एक फ़ंक्शन की गणना करता है <math>n</math> आदानों। एक सर्किट का आकार इसमें शामिल फाटकों की संख्या है और इसकी गहराई इनपुट गेट से आउटपुट गेट तक पथ की अधिकतम लंबाई है।
के साथ बूलियन सर्किट <math>n</math> इनपुट [[अंश]]्स [[निर्देशित अचक्रीय ग्राफ]] है जिसमें प्रत्येक नोड (आमतौर पर इस संदर्भ में गेट्स कहा जाता है) या तो [[इन-डिग्री]] 0 का इनपुट नोड होता है जिसे किसी द्वारा लेबल किया जाता है। <math>n</math> इनपुट बिट्स, AND गेट, OR गेट या NOT गेट। इनमें से गेट को आउटपुट गेट के रूप में नामित किया गया है। ऐसा सर्किट स्वाभाविक रूप से इसके फ़ंक्शन की गणना करता है <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> outputting <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> outputting <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 36: Line 36:
उपयोग किए गए सर्किट के परिवार पर कुछ प्रतिबंधों के तहत सुपरपोलिनोमियल निचली सीमाएं साबित हुई हैं। पहला कार्य जिसके लिए सुपरपोलिनोमियल सर्किट निचली सीमाएँ दिखाई गई थीं, समता फ़ंक्शन था, जो इसके इनपुट बिट्स मॉड्यूलो 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 का एक समूह होता है। कार्यों का यह परिवार मोनोटोन है और इसकी गणना सर्किट के एक परिवार द्वारा की जा सकती है, लेकिन यह दिखाया गया है कि इसकी गणना मोनोटोन सर्किट के बहुपद-आकार के परिवार द्वारा नहीं की जा सकती है (अर्थात, AND और OR गेट वाले सर्किट लेकिन बिना निषेध के)। 1985 में [[अलेक्जेंडर रज़बोरोव]] का मूल परिणाम<ref name="Razborov_1985"/>बाद में 1987 में अलोन और बोपना द्वारा एक घातीय-आकार के निचले हिस्से में सुधार किया गया।<ref name="Alon-Boppana_1987"/>2008 में, रॉसमैन<ref name="Rossman_2008"/>ने दिखाया कि AND, OR और NOT गेट्स वाले स्थिर-गहराई वाले सर्किटों के लिए आकार की आवश्यकता होती है <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 का समूह होता है। कार्यों का यह परिवार मोनोटोन है और इसकी गणना सर्किट के परिवार द्वारा की जा सकती है, लेकिन यह दिखाया गया है कि इसकी गणना मोनोटोन सर्किट के बहुपद-आकार के परिवार द्वारा नहीं की जा सकती है (अर्थात, AND और OR गेट वाले सर्किट लेकिन बिना निषेध के)। 1985 में [[अलेक्जेंडर रज़बोरोव]] का मूल परिणाम<ref name="Razborov_1985"/>बाद में 1987 में अलोन और बोपना द्वारा घातीय-आकार के निचले हिस्से में सुधार किया गया।<ref name="Alon-Boppana_1987"/>2008 में, रॉसमैन<ref name="Rossman_2008"/>ने दिखाया कि AND, OR और NOT गेट्स वाले स्थिर-गहराई वाले सर्किटों के लिए आकार की आवश्यकता होती है <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"/>


पूर्णांक विभाजन समस्या एकसमान TC0|TC में निहित है<sup>0</उप>।<ref name="Hesse_2001"/>
पूर्णांक विभाजन समस्या एकसमान TC0|TC में निहित है<sup>0</उप>।<ref name="Hesse_2001"/>
Line 45: Line 45:
== सर्किट निचली सीमा ==
== सर्किट निचली सीमा ==
सर्किट निचली सीमाएं आम तौर पर कठिन होती हैं। ज्ञात परिणाम शामिल हैं
सर्किट निचली सीमाएं आम तौर पर कठिन होती हैं। ज्ञात परिणाम शामिल हैं
* समता असमान 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|ACC<sup>0</sup> में बहुमत का कार्य शामिल नहीं है, यह केवल 2010 में [[रयान विलियम्स (कंप्यूटर वैज्ञानिक)]] ने साबित किया था {{nowrap|<math>\mathsf{NEXP} \not \subseteq \mathsf{ACC}^0</math>.<ref name="Williams_2011"/>}}
* जबकि यह संदेह है कि गैर-वर्दी वर्ग ACC0|ACC<sup>0</sup> में बहुमत का कार्य शामिल नहीं है, यह केवल 2010 में [[रयान विलियम्स (कंप्यूटर वैज्ञानिक)]] ने साबित किया था {{nowrap|<math>\mathsf{NEXP} \not \subseteq \mathsf{ACC}^0</math>.<ref name="Williams_2011"/>}}
यह खुला है कि क्या NEXPTIME के ​​पास असमान टीसी है<sup>0</sup> सर्किट।
यह खुला है कि क्या NEXPTIME के ​​पास असमान टीसी है<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 में, Carmosino, Impagliazzo, Kabanets और Kolokolova ने साबित कर दिया कि कुशल शिक्षण एल्गोरिदम के निर्माण के लिए प्राकृतिक गुणों का भी उपयोग किया जा सकता है।<ref name="Carmosino-Impagliazzo-Kabanets-Kolokolova_2016"/>
1997 में, रज़बोरोव और रुडिच ने दिखाया कि स्पष्ट बूलियन कार्यों के लिए कई ज्ञात सर्किट निचली सीमाएं संबंधित सर्किट वर्ग के विरुद्ध तथाकथित [[प्राकृतिक प्रमाण]] के अस्तित्व का संकेत देती हैं।<ref name="Razborov-Rudich_1997"/>दूसरी ओर, पी/पॉली के खिलाफ उपयोगी प्राकृतिक गुण मजबूत छद्म यादृच्छिक जनरेटर को तोड़ देंगे। इसे अक्सर मजबूत सर्किट निचली सीमा साबित करने के लिए प्राकृतिक सबूत बाधा के रूप में व्याख्या की जाती है। 2016 में, Carmosino, Impagliazzo, Kabanets और Kolokolova ने साबित कर दिया कि कुशल शिक्षण एल्गोरिदम के निर्माण के लिए प्राकृतिक गुणों का भी उपयोग किया जा सकता है।<ref name="Carmosino-Impagliazzo-Kabanets-Kolokolova_2016"/>
Line 55: Line 55:


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


== समय जटिलता से संबंध ==
== समय जटिलता से संबंध ==

Revision as of 21:01, 20 February 2023

[[/index.php?title=Special:MathShowImage&hash=b6252c47c600d72b4b0f484c229f580d&mode=mathml|thumb|right|उदाहरण बूलियन सर्किट। h> नोड AND गेट्स हैं, द नोड