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

From Vigyanwiki
No edit summary
No edit summary
 
(15 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Short description|Model of computational complexity}}
{{Short description|Model of computational complexity}}


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


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


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


=== बहुपद-समय की वर्दी ===
=== बहुपद-समय का समरूप ===
बूलियन सर्किट का परिवार <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>


 
=== लॉगस्थान समरूप ===
=== लॉगस्पेस वर्दी ===
बूलियन परिपथ का वर्ग <math>\{C_n:n \in \mathbb{N}\}</math> यदि नियतात्मक ट्यूरिंग मशीन M उपस्थ है, तो लॉगस्थान एक समान है, जैसे कि
बूलियन सर्किट का परिवार <math>\{C_n:n \in \mathbb{N}\}</math> यदि नियतात्मक ट्यूरिंग मशीन M मौजूद है, तो लॉगस्पेस एकसमान है, जैसे कि
* 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>
== इतिहास ==
== इतिहास ==
1949 में सर्किट जटिलता [[क्लाउड शैनन]] के पास वापस जाती है,<ref name="Shannon_1949"/>जिन्होंने सिद्ध किया कि n चरों पर लगभग सभी बूलियन कार्यों के लिए आकार Θ(2) के परिपथों की आवश्यकता होती है<sup>एन</sup>/n). इस तथ्य के बावजूद, जटिलता सिद्धांतवादी अब तक किसी भी स्पष्ट कार्य के लिए सुपरलीनियर लोअर बाउंड साबित करने में असमर्थ रहे हैं।
1949 में परिपथ जटिलता [[क्लाउड शैनन]] के पास वापस जाती है,<ref name="Shannon_1949"/> जिन्होंने सिद्ध किया कि n चरों पर लगभग सभी बूलियन कार्यों के लिए आकार Θ(2n/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"/>साबित हुआ कि यह सच है भले ही सर्किट गेट्स के साथ संवर्धित हो, इसके इनपुट बिट्स मॉडुलो कुछ विषम प्राइम पी के योग की गणना करता है।
 
क्लिक समस्या | के-क्लिक समस्या यह तय करने के लिए है कि क्या 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"/>


पूर्णांक विभाजन समस्या एकसमान TC0|TC में निहित है<sup>0</उप>।<ref name="Hesse_2001"/>
उपयोग किए गए परिपथ के वर्ग पर कुछ प्रतिबंधों के अनुसार अधिबहुपद निचली सीमाएं सिद्ध हुई हैं। पहला कार्य जिसके लिए अधिबहुपद परिपथ निचली सीमाएँ दिखाई गई थीं, समता फलन था, जो इसके इनपुट बिट्स मॉड्यूलो 2 के योग की गणना करता है। तथ्य यह है कि समानता 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"/> सिद्ध हुआ कि यह सच है तथापि परिपथ गेट्स के साथ संवर्धित हो, इसके इनपुट बिट्स मापांक कुछ विषम प्रधान P के योग की गणना करता है।


K-क्लिक समस्या यह तय करने के लिए है कि क्या n शिखर पर दिए गए ग्राफ में आकार K का समूह है। स्थिरांक n और k के किसी विशेष विकल्प के लिए, ग्राफ़ को बाइनरी में एन्कोड किया जा सकता है <math>{n \choose 2}</math> बिट्स, जो प्रत्येक संभावित किनारे के लिए इंगित करता है कि यह उपस्थ है या नहीं। फिर K-क्लिक समस्या को फलन के रूप में औपचारिक रूप दिया जाता है <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"/> ने दिखाया कि AND, OR और NOT गेट्स वाले स्थिर-गहराई वाले परिपथों के लिए आकार की आवश्यकता होती है <math>\Omega(n^{k/4})</math> औसत स्थितियों की जटिलता में भी K-क्लिक समस्या को हल करने के लिए। इसके अतिरिक्त, आकार का परिपथ है <math>n^{k/4+O(1)}</math> जो गणना करता है <math>f_k</math>.


== सर्किट निचली सीमा ==
1999 में, [[घाव एक बार|घाव बार]] और [[पियरे मैकेंजी]] ने बाद में दिखाया कि मोनोटोन एनसी पदानुक्रम अनंत है।<ref name="Raz-McKenzie_1999"/>
सर्किट निचली सीमाएं आम तौर पर कठिन होती हैं। ज्ञात परिणाम शामिल हैं
* समता असमान 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"/>}}
यह खुला है कि क्या 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"/>
पूर्णांक विभाजन समस्या एकसमान TC0|TC TC<sup>0</sup> में निहित है<sup>।<ref name="Hesse_2001"/>


1997 में, रज़बोरोव और रुडिच ने दिखाया कि स्पष्ट बूलियन कार्यों के लिए कई ज्ञात सर्किट निचली सीमाएं संबंधित सर्किट वर्ग के विरुद्ध तथाकथित [[प्राकृतिक प्रमाण]] के अस्तित्व का संकेत देती हैं।<ref name="Razborov-Rudich_1997"/>दूसरी ओर, पी/पॉली के खिलाफ उपयोगी प्राकृतिक गुण मजबूत छद्म यादृच्छिक जनरेटर को तोड़ देंगे। इसे अक्सर मजबूत सर्किट निचली सीमा साबित करने के लिए प्राकृतिक सबूत बाधा के रूप में व्याख्या की जाती है। 2016 में, Carmosino, Impagliazzo, Kabanets और Kolokolova ने साबित कर दिया कि कुशल शिक्षण एल्गोरिदम के निर्माण के लिए प्राकृतिक गुणों का भी उपयोग किया जा सकता है।<ref name="Carmosino-Impagliazzo-Kabanets-Kolokolova_2016"/>
== परिपथ निचली सीमा ==
परिपथ निचली सीमाएं सामान्यतः कठिन होती हैं। ज्ञात परिणाम सम्मिलित हैं
* 1983 [3] [4] में अजताई द्वारा और साथ ही 1984 में फुर्स्ट, सक्से और सिप्सर द्वारा सिद्ध किया गया,<ref name="Ajtai_1983"/><ref name="Ajtai-Komlós-Szemerédi_1983"/> समानता गैर-समान AC<sup>0</sup>में नहीं है। [5]।<ref name="Furst-Saxe-Sipser_1984"/>
*एलेंडर द्वारा प्रमाणित, वर्ग TC<sup>0</sup> PP में सख्ती से निहित है।<ref name="Allender_1997" />
*वर्ग S.P 2, PP[nb 1] और MA/1<ref name="Santhanam_2007" /> (MA एक बिट सलाह के साथ) किसी स्थिर k के लिए '''SIZE'''(''n<sup>k</sup>'') में नहीं हैं
* जबकि यह संदेह है कि गैर- समरूप वर्ग ACC0 में बहुमत का कार्य सम्मिलित नहीं है, यह केवल 2010 में [[रयान विलियम्स (कंप्यूटर वैज्ञानिक)]] ने सिद्ध किया था {{nowrap|<math>\mathsf{NEXP} \not \subseteq \mathsf{ACC}^0</math>.<ref name="Williams_2011"/>}}
यह खुला है कि क्या नेक्स्पटाइम के ​​पास असमान TC<sup>0</sup> है परिपथ। PP<ref group="nb" name="NB1"/> and [[MA (complexity)|MA]]/1<ref name="Santhanam_2007"/> (MA with one bit of advice) are not in '''SIZE'''(''n<sup>k</sup>'') for any constant k.


परिपथ लोअर बाउंड्स के साक्ष्य [[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"/>
== जटिलता वर्ग ==
== जटिलता वर्ग ==
कई सर्किट जटिलता वर्गों को वर्ग पदानुक्रमों के संदर्भ में परिभाषित किया गया है। प्रत्येक गैर-ऋणात्मक पूर्णांक 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 गेट्स का उपयोग करना। इन सभी वर्गों की संघ एनसी चर्चा का विषय है। असीमित फैन-इन गेट्स पर विचार करके, कक्षाएं AC (जटिलता) | AC<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>
== यह भी देखें ==
== यह भी देखें ==
* [[सर्किट न्यूनीकरण]]
* [[सर्किट न्यूनीकरण|परिपथ न्यूनीकरण]]


==टिप्पणियाँ==
==टिप्पणियाँ==
Line 69: Line 63:
<ref group="nb" name="NB1">See [[Karp-Lipton theorem#Application for circuit lower bounds - Kannan's theorem|proof]].</ref>
<ref group="nb" name="NB1">See [[Karp-Lipton theorem#Application for circuit lower bounds - Kannan's theorem|proof]].</ref>
}}
}}


==संदर्भ==
==संदर्भ==
Line 92: Line 85:
<ref name="Alon-Boppana_1987">{{cite journal |author-first1=Noga |author-last1=Alon |author-link1=Noga Alon |author-first2=Ravi B. |author-last2=Boppana |title=The monotone circuit complexity of Boolean functions |journal=[[Combinatorica]] |volume=7 |date=1987 |number=1 |pages=1–22 |doi=10.1007/bf02579196 |citeseerx=10.1.1.300.9623}}</ref>
<ref name="Alon-Boppana_1987">{{cite journal |author-first1=Noga |author-last1=Alon |author-link1=Noga Alon |author-first2=Ravi B. |author-last2=Boppana |title=The monotone circuit complexity of Boolean functions |journal=[[Combinatorica]] |volume=7 |date=1987 |number=1 |pages=1–22 |doi=10.1007/bf02579196 |citeseerx=10.1.1.300.9623}}</ref>
}}
}}


==अग्रिम पठन==
==अग्रिम पठन==
Line 98: Line 90:
* {{cite book |author-last=Wegener |author-first=Ingo |author-link=Ingo Wegener |title=The Complexity of Boolean Functions |series=Wiley–Teubner Series in Computer Sciences |publisher=[[John Wiley & Sons Ltd.]], and [[B. G. Teubner Verlag]], Stuttgart |date=1987 |orig-date=November 1986 |location=Frankfurt am Main/Bielefeld, Germany |isbn=3-519-02107-2<!-- Teubner --> |lccn=87-10388}} (xii+457 pages) (NB. At the time an influential textbook on the subject, commonly known as the "Blue Book". Also available for [http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/ download (PDF)] at the [[Electronic Colloquium on Computational Complexity]].)
* {{cite book |author-last=Wegener |author-first=Ingo |author-link=Ingo Wegener |title=The Complexity of Boolean Functions |series=Wiley–Teubner Series in Computer Sciences |publisher=[[John Wiley & Sons Ltd.]], and [[B. G. Teubner Verlag]], Stuttgart |date=1987 |orig-date=November 1986 |location=Frankfurt am Main/Bielefeld, Germany |isbn=3-519-02107-2<!-- Teubner --> |lccn=87-10388}} (xii+457 pages) (NB. At the time an influential textbook on the subject, commonly known as the "Blue Book". Also available for [http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/ download (PDF)] at the [[Electronic Colloquium on Computational Complexity]].)
* {{cite web |title=Lecture notes for a course of Uri Zwick on circuit complexity |author-first=Uri |author-last=Zwick |author-link=Uri Zwick |url=http://www.cs.tau.ac.il/~zwick/scribe-boolean.html}}
* {{cite web |title=Lecture notes for a course of Uri Zwick on circuit complexity |author-first=Uri |author-last=Zwick |author-link=Uri Zwick |url=http://www.cs.tau.ac.il/~zwick/scribe-boolean.html}}
[[Category: सर्किट जटिलता | सर्किट जटिलता ]] [[Category: कम्प्यूटेशनल जटिलता सिद्धांत]]


[[Category: Machine Translated Page]]
[[Category:Created On 16/02/2023]]
[[Category:Created On 16/02/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with reference errors]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Template documentation pages|Short description/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]

Latest revision as of 19:34, 7 March 2023

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

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

बूलियन सर्किट के संदर्भ में परिभाषित जटिलता वर्गों में AC0, AC, TC0, NC1, NC, और P/poly सम्मिलित हैं।

आकार और गहराई

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

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

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

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

एकरूपता

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

बहुपद-समय का समरूप

बूलियन परिपथ का वर्ग यदि नियतात्मक ट्यूरिंग मशीन M उपस्थ है, तो बहुपद-समय एक समान है, जैसे कि

  • एम बहुपद समय में चलता है
  • सभी के लिए , M का विवरण आउटपुट करता है इनपुट पर

लॉगस्थान समरूप

बूलियन परिपथ का वर्ग यदि नियतात्मक ट्यूरिंग मशीन M उपस्थ है, तो लॉगस्थान एक समान है, जैसे कि

  • M लघुगणकीय स्थान में चलता है
  • सभी के लिए , M का विवरण आउटपुट करता है इनपुट पर

इतिहास

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

उपयोग किए गए परिपथ के वर्ग पर कुछ प्रतिबंधों के अनुसार अधिबहुपद निचली सीमाएं सिद्ध हुई हैं। पहला कार्य जिसके लिए अधिबहुपद परिपथ निचली सीमाएँ दिखाई गई थीं, समता फलन था, जो इसके इनपुट बिट्स मॉड्यूलो 2 के योग की गणना करता है। तथ्य यह है कि समानता AC0 में समाहित नहीं है। पहली बार 1983 में अजताई द्वारा स्वतंत्र रूप से स्थापित किया गया था[3][4] और 1984 में फुर्स्ट, सक्से और सिप्सर द्वारा।[5] बाद में 1987 में जोहान हस्ताद द्वारा किए गए सुधारों ने स्थापित किया[6] कि समता फलन की गणना करने वाले निरंतर-गहराई वाले परिपथ के किसी भी वर्ग को घातीय आकार की आवश्यकता होती है। रज़बोरोव के परिणाम का विस्तार,[7]1987 में स्मोलेंस्की[8] सिद्ध हुआ कि यह सच है तथापि परिपथ गेट्स के साथ संवर्धित हो, इसके इनपुट बिट्स मापांक कुछ विषम प्रधान P के योग की गणना करता है।

K-क्लिक समस्या यह तय करने के लिए है कि क्या n शिखर पर दिए गए ग्राफ में आकार K का समूह है। स्थिरांक n और k के किसी विशेष विकल्प के लिए, ग्राफ़ को बाइनरी में एन्कोड किया जा सकता है बिट्स, जो प्रत्येक संभावित किनारे के लिए इंगित करता है कि यह उपस्थ है या नहीं। फिर K-क्लिक समस्या को फलन के रूप में औपचारिक रूप दिया जाता है ऐसा है कि आउटपुट 1 यदि और केवल तभी जब स्ट्रिंग द्वारा एन्कोड किए गए ग्राफ़ में आकार k का समूह होता है। कार्यों का यह वर्ग मोनोटोन है और इसकी गणना परिपथ के वर्ग द्वारा की जा सकती है, किन्तु यह दिखाया गया है कि इसकी गणना मोनोटोन परिपथ के बहुपद-आकार के वर्ग द्वारा नहीं की जा सकती है (अर्थात, एंड और और गेट वाले परिपथ किन्तु बिना निषेध के)। 1985 में अलेक्जेंडर रज़बोरोव का मूल परिणाम[7] बाद में 1987 में अलोन और बोपना द्वारा घातीय-आकार के निचले हिस्से में सुधार किया गया।[9] 2008 में, रॉसमैन[10] ने दिखाया कि AND, OR और NOT गेट्स वाले स्थिर-गहराई वाले परिपथों के लिए आकार की आवश्यकता होती है औसत स्थितियों की जटिलता में भी K-क्लिक समस्या को हल करने के लिए। इसके अतिरिक्त, आकार का परिपथ है जो गणना करता है .

1999 में, घाव बार और पियरे मैकेंजी ने बाद में दिखाया कि मोनोटोन एनसी पदानुक्रम अनंत है।[11]

पूर्णांक विभाजन समस्या एकसमान TC0|TC TC0 में निहित है।[12]

परिपथ निचली सीमा

परिपथ निचली सीमाएं सामान्यतः कठिन होती हैं। ज्ञात परिणाम सम्मिलित हैं

  • 1983 [3] [4] में अजताई द्वारा और साथ ही 1984 में फुर्स्ट, सक्से और सिप्सर द्वारा सिद्ध किया गया,[3][4] समानता गैर-समान AC0में नहीं है। [5]।[5]
  • एलेंडर द्वारा प्रमाणित, वर्ग TC0 PP में सख्ती से निहित है।[13]
  • वर्ग S.P 2, PP[nb 1] और MA/1[14] (MA एक बिट सलाह के साथ) किसी स्थिर k के लिए SIZE(nk) में नहीं हैं
  • जबकि यह संदेह है कि गैर- समरूप वर्ग ACC0 में बहुमत का कार्य सम्मिलित नहीं है, यह केवल 2010 में रयान विलियम्स (कंप्यूटर वैज्ञानिक) ने सिद्ध किया था .[15]

यह खुला है कि क्या नेक्स्पटाइम के ​​पास असमान TC0 है परिपथ। PP[nb 1] and MA/1[14] (MA with one bit of advice) are not in SIZE(nk) for any constant k.

परिपथ लोअर बाउंड्स के साक्ष्य डेरनडोमाईजेशन से दृढ़ता से जुड़े हुए हैं। साक्ष्य है कि इसका मतलब यह होगा कि या तो या उस स्थायी की गणना बहुपद आकार और बहुपद डिग्री के गैर-समान अंकगणितीय परिपथ (बहुपद) द्वारा नहीं की जा सकती।[16]

1997 में, रज़बोरोव और रुडिच ने दिखाया कि स्पष्ट बूलियन कार्यों के लिए कई ज्ञात परिपथ निचली सीमाएं संबंधित परिपथ वर्ग के विरुद्ध तथाकथित प्राकृतिक प्रमाण के अस्तित्व का संकेत देती हैं।[17] दूसरी ओर, पी/पॉली के खिलाफ उपयोगी प्राकृतिक गुण शक्तिशाली छद्म यादृच्छिक जनरेटर को तोड़ देंगे। इसे अधिकांशतः शक्तिशाली परिपथ निचली सीमा सिद्ध करने के लिए प्राकृतिक साक्ष्य बाधा के रूप में व्याख्या की जाती है। 2016 में, कारमोसिनो, इम्पैग्लियाज़ो, कबनेट्स और कोलोकोलोवा ने सिद्ध कर दिया कि कुशल शिक्षण एल्गोरिदम के निर्माण के लिए प्राकृतिक गुणों का भी उपयोग किया जा सकता है।[18]

जटिलता वर्ग

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

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

यदि कोई निश्चित भाषा, , कॉम्प्लेक्सिटी क्लास | टाइम-कॉम्प्लेक्सिटी क्लास से संबंधित है किसी फलन के लिए , तब परिपथ जटिलता है . यदि भाषा को स्वीकार करने वाली ट्यूरिंग मशीन ट्यूरिंग मशीन समकक्ष है (जिसका अर्थ है कि यह इनपुट की परवाह किए बिना समान मेमोरी सेल को पढ़ती और लिखती है), तो परिपथ जटिलता है .[19]

यह भी देखें

टिप्पणियाँ

  1. ↑ See proof.

संदर्भ

  1. ↑ Sipser, Michael (1997). Introduction to the theory of computation (1 ed.). Boston, USA: PWS Publishing Company. p. 324.
  2. ↑ Shannon, Claude Elwood (1949). "The synthesis of two-terminal switching circuits". Bell System Technical Journal. 28 (1): 59–98. doi:10.1002/j.1538-7305.1949.tb03624.x.
  3. ↑ 3.0 3.1 Ajtai, Miklós (1983). "-formulae on finite structures". Annals of Pure and Applied Logic. 24: 1–24. doi:10.1016/0168-0072(83)90038-6.
  4. ↑ 4.0 4.1 Ajtai, Miklós; Komlós, János; Szemerédi, Endre (1983). An 0(n log n) sorting network. pp. 1–9. ISBN 978-0-89791-099-6. {{cite book}}: |journal= ignored (help)
  5. ↑ 5.0 5.1 Furst, Merrick L.; Saxe, James Benjamin; Sipser, Michael Fredric (1984). "Parity, circuits, and the polynomial-time hierarchy". Mathematical Systems Theory. 17 (1): 13–27. doi:10.1007/BF01744431. MR 0738749.
  6. ↑ Håstad, Johan Torkel (1987). Computational limitations of small depth circuits (PDF) (Ph.D. thesis). Massachusetts Institute of Technology.
  7. ↑ 7.0 7.1 Razborov, Aleksandr Aleksandrovich (1985). "Lower bounds on the monotone complexity of some Boolean functions". Soviet Mathematics - Doklady. 31: 354–357. ISSN 0197-6788.
  8. ↑ Smolensky, Roman (1987). "Algebraic methods in the theory of lower bounds for Boolean circuit complexity". Proceedings of the 19th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery. pp. 77–82. doi:10.1145/28395.28404.
  9. ↑ Alon, Noga; Boppana, Ravi B. (1987). "The monotone circuit complexity of Boolean functions". Combinatorica. 7 (1): 1–22. CiteSeerX 10.1.1.300.9623. doi:10.1007/bf02579196.
  10. ↑ Rossman, Benjamin E. (2008). "On the constant-depth complexity of k-clique". STOC 2008: Proceedings of the 40th annual ACM symposium on Theory of computing. Association for Computing Machinery. pp. 721–730. doi:10.1145/1374376.1374480.
  11. ↑ Raz, Ran; McKenzie, Pierre (1999). "Separation of the monotone NC hierarchy". Combinatorica. 19 (3): 403–435. doi:10.1007/s004930050062.
  12. ↑ Hesse, William (2001). "Division is in uniform TC0". Proceedings of the 28th International Colloquium on Automata, Languages and Programming. Springer Verlag. pp. 104–114.
  13. ↑ Allender, Eric Warren, ed. (1997). "Circuit Complexity before the Dawn of the New Millennium" (PDF). [1] (NB. A 1997 survey of the field by Eric Allender.)
  14. ↑ 14.0 14.1 Santhanam, Rahul (2007). "Circuit lower bounds for Merlin-Arthur classes". STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. pp. 275–283. CiteSeerX 10.1.1.92.4422. doi:10.1145/1250790.1250832.
  15. ↑ Williams, Richard Ryan (2011). "Non-Uniform ACC Circuit Lower Bounds" (PDF). CCC 2011: Proceedings of the 26th Annual IEEE Conference on Computational Complexity. pp. 115–125. doi:10.1109/CCC.2011.36.
  16. ↑ Kabanets, Valentine [at Wikidata]; Impagliazzo, Russell Graham (2004). "Derandomizing polynomial identity tests means proving circuit lower bounds". Computational Complexity. 13 (1): 1–46. doi:10.1007/s00037-004-0182-6.
  17. ↑ Razborov, Aleksandr Aleksandrovich; Rudich, Steven (1997). "Natural proofs". Journal of Computer and System Sciences. Vol. 55. pp. 24–35.
  18. ↑ Carmosino, Marco; Impagliazzo, Russell Graham; Kabanets, Valentine [at Wikidata]; Kolokolova, Antonina (2016). "Learning algorithms from natural proofs". Computational Complexity Conference.
  19. ↑ Pippenger, Nicholas; Fischer, Michael J. (1979), "Relations Among Complexity Measures", Journal of the ACM, 26 (3): 361–381, doi:10.1145/322123.322138

अग्रिम पठन

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=सर्किट_जटिलता&oldid=101623’