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

Revision as of 21:18, 20 February 2023

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

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

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

आकार और गहराई

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

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

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

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

एकरूपता

बूलियन सर्किट तथाकथित गैर-समान सार मशीन के प्रमुख उदाहरणों में से हैं, इस अर्थ में कि अलग-अलग लंबाई के इनपुट को अलग-अलग सर्किट द्वारा संसाधित किया जाता है, इसके विपरीत ट्यूरिंग मशीन जैसे समान मॉडल के विपरीत, जहां सभी संभव के लिए ही कम्प्यूटेशनल डिवाइस का उपयोग किया जाता है। इनपुट लंबाई। व्यक्तिगत कम्प्यूटेशनल समस्या इस प्रकार बूलियन सर्किट के विशेष परिवार से जुड़ी हुई है $C_{1},C_{2},\dots$ जहां प्रत्येक $C_{n}$ n बिट्स का सर्किट हैंडलिंग इनपुट है। इन परिवारों पर अधिकांशतः एकरूपता की शर्त लगाई जाती है, जिसके लिए कुछ संभावित कम्प्यूटेशनल संसाधन | संसाधन-बद्ध ट्यूरिंग मशीन के अस्तित्व की आवश्यकता होती है, जो इनपुट एन पर, व्यक्तिगत सर्किट का विवरण तैयार करती है। $C_{n}$ . जब इस ट्यूरिंग मशीन का रनिंग टाइम बहुपद n में होता है, तो सर्किट परिवार को P-वर्दी कहा जाता है। DLOGTIME- एकरूपता की कठोर आवश्यकता एसी जैसे उथले-गहराई वाले सर्किट-वर्गों के अध्ययन में विशेष रुचि रखती है⁰ या टीसी^{0</उप>। जब कोई संसाधन सीमा निर्दिष्ट नहीं की जाती है, तो भाषा पुनरावर्ती होती है (अर्थात, ट्यूरिंग मशीन द्वारा तय की जा सकती है) यदि और केवल यदि भाषा बूलियन सर्किट के समान परिवार द्वारा तय की जाती है।}

बहुपद-समय की वर्दी

बूलियन सर्किट का परिवार $\{C_{n}:n\in \mathbb {N} \}$ यदि नियतात्मक ट्यूरिंग मशीन M उपस्थ है, तो बहुपद-समय एकसमान है, जैसे कि

एम बहुपद समय में चलता है
सभी के लिए $n\in \mathbb {N}$ , M का विवरण आउटपुट करता है $C_{n}$ इनपुट पर $1^{n}$

लॉगस्पेस वर्दी

बूलियन सर्किट का परिवार $\{C_{n}:n\in \mathbb {N} \}$ यदि नियतात्मक ट्यूरिंग मशीन M उपस्थ है, तो लॉगस्पेस एकसमान है, जैसे कि

एम लॉगरिदमिक स्पेस में चलता है
सभी के लिए $n\in \mathbb {N}$ , M का विवरण आउटपुट करता है $C_{n}$ इनपुट पर $1^{n}$

इतिहास

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

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

क्लिक समस्या | के-क्लिक समस्या यह तय करने के लिए है कि क्या n शिखर पर दिए गए ग्राफ में आकार के आकार का चक्कर है। स्थिरांक n और k के किसी विशेष विकल्प के लिए, ग्राफ़ को बाइनरी में एन्कोड किया जा सकता है ${n \choose 2}$ बिट्स, जो प्रत्येक संभावित किनारे के लिए इंगित करता है कि यह उपस्थ है या नहीं। फिर के-क्लिक समस्या को समारोह के रूप में औपचारिक रूप दिया जाता है $f_{k}:\{0,1\}^{n \choose 2}\to \{0,1\}$ ऐसा है कि $f_{k}$ आउटपुट 1 यदि और केवल तभी जब स्ट्रिंग द्वारा एन्कोड किए गए ग्राफ़ में आकार k का समूह होता है। कार्यों का यह परिवार मोनोटोन है और इसकी गणना सर्किट के परिवार द्वारा की जा सकती है, किन्तु यह दिखाया गया है कि इसकी गणना मोनोटोन सर्किट के बहुपद-आकार के परिवार द्वारा नहीं की जा सकती है (अर्थात, AND और OR गेट वाले सर्किट किन्तु बिना निषेध के)। 1985 में अलेक्जेंडर रज़बोरोव का मूल परिणाम^[7]बाद में 1987 में अलोन और बोपना द्वारा घातीय-आकार के निचले हिस्से में सुधार किया गया।^[9]2008 में, रॉसमैन^[10]ने दिखाया कि AND, OR और NOT गेट्स वाले स्थिर-गहराई वाले सर्किटों के लिए आकार की आवश्यकता होती है $\Omega (n^{k/4})$ औसत स्थितियोंे की जटिलता में भी के-क्लिक समस्या को हल करने के लिए। इसके अतिरिक्त, आकार का सर्किट है $n^{k/4+O(1)}$ जो गणना करता है $f_{k}$ .

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

पूर्णांक विभाजन समस्या एकसमान TC0|TC में निहित है^{0</उप>।^[12]}

सर्किट निचली सीमा

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

समता असमान AC0|AC में नहीं है⁰, अजताई द्वारा 1983 में सिद्ध किया गया^[3]^[4]साथ ही 1984 में फुर्स्ट, सक्से और सिप्सर द्वारा।^[5]* यूनिफ़ॉर्म TC0|TC⁰ पीपी (जटिलता) में सख्ती से समाहित है, जिसे एलेंडर ने सिद्ध किया है।^[13]* वर्ग S2P (जटिलता)|S^P
₂, पीपी^{[nb 1]}और एमए (जटिलता)/1^[14]( सलाह के साथ एमए) आकार में नहीं हैं ( एन^k) किसी भी स्थिर k के लिए।
जबकि यह संदेह है कि गैर-वर्दी वर्ग ACC0|ACC⁰ में बहुमत का कार्य सम्मिलित नहीं है, यह केवल 2010 में रयान विलियम्स (कंप्यूटर वैज्ञानिक) ने सिद्ध किया था ${\mathsf {NEXP}}\not \subseteq {\mathsf {ACC}}^{0}$ .^[15]

यह खुला है कि क्या NEXPTIME के पास असमान टीसी है⁰ सर्किट।

सर्किट लोअर बाउंड्स के सबूत derandomization से दृढ़ता से जुड़े हुए हैं। सबूत है कि ${\mathsf {P}}={\mathsf {BPP}}$ इसका मतलब यह होगा कि या तो ${\mathsf {NEXP}}\not \subseteq {\mathsf {P/poly}}$ या उस स्थायी की गणना बहुपद आकार और बहुपद डिग्री के गैर-समान अंकगणितीय सर्किट (बहुपद) द्वारा नहीं की जा सकती।^[16]

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

जटिलता वर्ग

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

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

यदि कोई निश्चित भाषा, $A$ , कॉम्प्लेक्सिटी क्लास | टाइम-कॉम्प्लेक्सिटी क्लास से संबंधित है ${\text{TIME}}(t(n))$ किसी समारोह के लिए $t:\mathbb {N} \to \mathbb {N}$ , तब $A$ सर्किट जटिलता है ${\mathcal {O}}(t(n)\log t(n))$ . यदि भाषा को स्वीकार करने वाली ट्यूरिंग मशीन ट्यूरिंग मशीन समकक्ष है (जिसका अर्थ है कि यह इनपुट की परवाह किए बिना समान मेमोरी सेल को पढ़ती और लिखती है), तो $A$ सर्किट जटिलता है ${\mathcal {O}}(t(n))$ .^[19]

यह भी देखें

सर्किट न्यूनीकरण

संदर्भ

↑ Sipser, Michael (1997). Introduction to the theory of computation (1 ed.). Boston, USA: PWS Publishing Company. p. 324.
↑ 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.0 ^3.1 Ajtai, Miklós (1983). " $\Sigma _{1}^{1}$ -formulae on finite structures". Annals of Pure and Applied Logic. 24: 1–24. doi:10.1016/0168-0072(83)90038-6.
↑ ^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.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.
↑ Håstad, Johan Torkel (1987). Computational limitations of small depth circuits (PDF) (Ph.D. thesis). Massachusetts Institute of Technology.
↑ ^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.
↑ 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.
↑ 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.
↑ 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.
↑ Raz, Ran; McKenzie, Pierre (1999). "Separation of the monotone NC hierarchy". Combinatorica. 19 (3): 403–435. doi:10.1007/s004930050062.
↑ Hesse, William (2001). "Division is in uniform TC⁰". Proceedings of the 28th International Colloquium on Automata, Languages and Programming. Springer Verlag. pp. 104–114.
↑ 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.)
↑ 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.
↑ 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.
↑ 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.
↑ Razborov, Aleksandr Aleksandrovich; Rudich, Steven (1997). "Natural proofs". Journal of Computer and System Sciences. Vol. 55. pp. 24–35.
↑ Carmosino, Marco; Impagliazzo, Russell Graham; Kabanets, Valentine [at Wikidata]; Kolokolova, Antonina (2016). "Learning algorithms from natural proofs". Computational Complexity Conference.
↑ Pippenger, Nicholas; Fischer, Michael J. (1979), "Relations Among Complexity Measures", Journal of the ACM, 26 (3): 361–381, doi:10.1145/322123.322138

अग्रिम पठन

Vollmer, Heribert [in Deutsch] (1999). Introduction to Circuit Complexity: a Uniform Approach. Texts in Theoretical Computer Science. An EATCS Series. Springer Verlag. ISBN 978-3-540-64310-4.
Wegener, Ingo (1987) [November 1986]. The Complexity of Boolean Functions. Wiley–Teubner Series in Computer Sciences. Frankfurt am Main/Bielefeld, Germany: John Wiley & Sons Ltd., and B. G. Teubner Verlag, Stuttgart. ISBN 3-519-02107-2. 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 download (PDF) at the Electronic Colloquium on Computational Complexity.)
Zwick, Uri. "Lecture notes for a course of Uri Zwick on circuit complexity".

[NB1-14] See proof.

[Sipser_1997-1] Sipser, Michael (1997). Introduction to the theory of computation (1 ed.). Boston, USA: PWS Publishing Company. p. 324.

[Shannon_1949-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.

[Ajtai_1983-3] 3.0 ^3.1 Ajtai, Miklós (1983). " $\Sigma _{1}^{1}$ -formulae on finite structures". Annals of Pure and Applied Logic. 24: 1–24. doi:10.1016/0168-0072(83)90038-6.

[Ajtai-Komlós-Szemerédi_1983-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)

[Furst-Saxe-Sipser_1984-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.

[Håstad_1987-6] Håstad, Johan Torkel (1987). Computational limitations of small depth circuits (PDF) (Ph.D. thesis). Massachusetts Institute of Technology.

[Razborov_1985-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.

[Smolensky_1987-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.

[Alon-Boppana_1987-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.

[Rossman_2008-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.

[Raz-McKenzie_1999-11] Raz, Ran; McKenzie, Pierre (1999). "Separation of the monotone NC hierarchy". Combinatorica. 19 (3): 403–435. doi:10.1007/s004930050062.

[Hesse_2001-12] Hesse, William (2001). "Division is in uniform TC⁰". Proceedings of the 28th International Colloquium on Automata, Languages and Programming. Springer Verlag. pp. 104–114.

[Allender_1997-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.)

[Santhanam_2007-15] 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.

[Williams_2011-16] 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.

[Kabanets-Impagliazzo_2004-17] 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.

[Razborov-Rudich_1997-18] Razborov, Aleksandr Aleksandrovich; Rudich, Steven (1997). "Natural proofs". Journal of Computer and System Sciences. Vol. 55. pp. 24–35.

[Carmosino-Impagliazzo-Kabanets-Kolokolova_2016-19] Carmosino, Marco; Impagliazzo, Russell Graham; Kabanets, Valentine [at Wikidata]; Kolokolova, Antonina (2016). "Learning algorithms from natural proofs". Computational Complexity Conference.

[20] Pippenger, Nicholas; Fischer, Michael J. (1979), "Relations Among Complexity Measures", Journal of the ACM, 26 (3): 361–381, doi:10.1145/322123.322138

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[nb 1]

[14]

[15]

[16]

[17]

[18]

[19]

@@ Line 1: / Line 1: @@
 {{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> (नीचे देखें)।
+[[/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> [[पी (जटिलता)]] और [[एनपी (जटिलता)]] को अलग करेगा (नीचे देखें)।
+स्पष्ट बूलियन कार्यों की गणना करने वाले बूलियन सर्किट के आकार पर निचली सीमा प्रदान करना जटिलता वर्गों को अलग करने का  लोकप्रिय विधि है। उदाहरण के लिए, 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>.
-ये धारणाएं सामान्यीकृत होती हैं जब कोई किसी भाषा की सर्किट जटिलता पर विचार करता है जिसमें अलग-अलग बिट लंबाई वाले तार होते हैं, विशेष रूप से अनंत [[औपचारिक भाषा]]एं। हालाँकि, बूलियन सर्किट केवल  निश्चित संख्या में इनपुट बिट्स की अनुमति देते हैं। इस प्रकार, कोई एकल बूलियन सर्किट ऐसी भाषा तय करने में सक्षम नहीं है। इस संभावना को ध्यान में रखते हुए, सर्किट के परिवारों पर विचार किया जाता है <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>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>
@@ 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>
@@ Line 32: / Line 32: @@
 == इतिहास ==
-में सर्किट जटिलता [[क्लाउड शैनन]] के पास वापस जाती है,<ref name="Shannon_1949"/>जिन्होंने सिद्ध किया कि n चरों पर लगभग सभी बूलियन कार्यों के लिए आकार Θ(2) के परिपथों की आवश्यकता होती है<sup>एन</sup>/n). इस तथ्य के बावजूद, जटिलता सिद्धांतवादी अब तक किसी भी स्पष्ट कार्य के लिए सुपरलीनियर लोअर बाउंड साबित करने में असमर्थ रहे हैं।
+में सर्किट जटिलता [[क्लाउड शैनन]] के पास वापस जाती है,<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 का  समूह होता है। कार्यों का यह परिवार मोनोटोन है और इसकी गणना सर्किट के  परिवार द्वारा की जा सकती है, लेकिन यह दिखाया गया है कि इसकी गणना मोनोटोन सर्किट के बहुपद-आकार के परिवार द्वारा नहीं की जा सकती है (अर्थात, 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>.
 में, [[घाव एक बार|घाव  बार]] और [[पियरे मैकेंजी]] ने बाद में दिखाया कि मोनोटोन एनसी पदानुक्रम अनंत है।<ref name="Raz-McKenzie_1999"/>
@@ Line 44: / Line 44: @@
 == सर्किट निचली सीमा ==
-सर्किट निचली सीमाएं आम तौर पर कठिन होती हैं। ज्ञात परिणाम शामिल हैं
+सर्किट निचली सीमाएं सामान्यतः कठिन होती हैं। ज्ञात परिणाम सम्मिलित हैं
 * समता असमान 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> सर्किट।
 सर्किट लोअर बाउंड्स के सबूत [[derandomization]] से दृढ़ता से जुड़े हुए हैं।  सबूत है कि <math>\mathsf{P} = \mathsf{BPP}</math> इसका मतलब यह होगा कि या तो <math>\mathsf{NEXP} \not \subseteq \mathsf{P/poly}</math> या उस स्थायी की गणना बहुपद आकार और बहुपद डिग्री के गैर-समान अंकगणितीय सर्किट (बहुपद) द्वारा नहीं की जा सकती।<ref name="Kabanets-Impagliazzo_2004"/>
-में, रज़बोरोव और रुडिच ने दिखाया कि स्पष्ट बूलियन कार्यों के लिए कई ज्ञात सर्किट निचली सीमाएं संबंधित सर्किट वर्ग के विरुद्ध तथाकथित [[प्राकृतिक प्रमाण]] के अस्तित्व का संकेत देती हैं।<ref name="Razborov-Rudich_1997"/>दूसरी ओर, पी/पॉली के खिलाफ उपयोगी प्राकृतिक गुण मजबूत छद्म यादृच्छिक जनरेटर को तोड़ देंगे। इसे अक्सर मजबूत सर्किट निचली सीमा साबित करने के लिए प्राकृतिक सबूत बाधा के रूप में व्याख्या की जाती है। 2016 में, Carmosino, Impagliazzo, Kabanets और Kolokolova ने साबित कर दिया कि कुशल शिक्षण एल्गोरिदम के निर्माण के लिए प्राकृतिक गुणों का भी उपयोग किया जा सकता है।<ref name="Carmosino-Impagliazzo-Kabanets-Kolokolova_2016"/>
+में, रज़बोरोव और रुडिच ने दिखाया कि स्पष्ट बूलियन कार्यों के लिए कई ज्ञात सर्किट निचली सीमाएं संबंधित सर्किट वर्ग के विरुद्ध तथाकथित [[प्राकृतिक प्रमाण]] के अस्तित्व का संकेत देती हैं।<ref name="Razborov-Rudich_1997"/>दूसरी ओर, पी/पॉली के खिलाफ उपयोगी प्राकृतिक गुण शक्तिशाली  छद्म यादृच्छिक जनरेटर को तोड़ देंगे। इसे अधिकांशतः शक्तिशाली  सर्किट निचली सीमा सिद्ध करने के लिए प्राकृतिक सबूत बाधा के रूप में व्याख्या की जाती है। 2016 में, Carmosino, Impagliazzo, Kabanets और Kolokolova ने सिद्ध कर दिया कि कुशल शिक्षण एल्गोरिदम के निर्माण के लिए प्राकृतिक गुणों का भी उपयोग किया जा सकता है।<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 गेट्स का उपयोग करना। इन सभी वर्गों की संघ एनसी चर्चा का विषय है। असीमित फैन-इन गेट्स पर विचार करके, कक्षाएं एसी (जटिलता) | एसी<sup>i</sup> और AC (जो NC के बराबर है) की रचना की जा सकती है। गेट्स के विभिन्न समुच्चयों की अनुमति देकर  ही आकार और गहराई प्रतिबंधों के साथ कई अन्य सर्किट जटिलता वर्गों का निर्माण किया जा सकता है।
 == समय जटिलता से संबंध ==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 21:18, 20 February 2023

Contents

आकार और गहराई

एकरूपता

बहुपद-समय की वर्दी

लॉगस्पेस वर्दी

इतिहास

सर्किट निचली सीमा

जटिलता वर्ग

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

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 21:18, 20 February 2023

आकार और गहराई

एकरूपता

बहुपद-समय की वर्दी

लॉगस्पेस वर्दी

इतिहास

सर्किट निचली सीमा

जटिलता वर्ग

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

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories