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

Revision as of 14:36, 3 March 2023

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

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

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

आकार और गहराई

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

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

ये धारणाएं सामान्यीकृत होती हैं जब कोई किसी भाषा की परिपथ जटिलता पर विचार करता है जिसमें अलग-अलग बिट लंबाई वाले तार होते हैं, विशेष रूप से अनंत औपचारिक भाषाएं। यद्यपि, बूलियन परिपथ केवल निश्चित संख्या में इनपुट बिट्स की अनुमति देते हैं। इस प्रकार, कोई एकल बूलियन परिपथ ऐसी भाषा तय करने में सक्षम नहीं है। इस संभावना को ध्यान में रखते हुए, परिपथ के वर्गों पर विचार किया जाता है $C_{1},C_{2},\ldots$ जहां प्रत्येक $C_{n}$ आकार के इनपुट स्वीकार करता है $n$ . प्रत्येक परिपथ वर्ग परिपथ द्वारा स्वाभाविक रूप से भाषा उत्पन्न करेगा $C_{n}$ आउटपुटिंग $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- समरूप कहा जाता है। डीलॉगटाइम- एकरूपता की कठोर आवश्यकता एसी जैसे उथले-गहराई वाले परिपथ-वर्गों के अध्ययन में विशेष रुचि रखती है AC⁰ या TC⁰ जब कोई संसाधन सीमा निर्दिष्ट नहीं की जाती है, तो एक भाषा पुनरावर्ती होती है (यानी, ट्यूरिंग मशीन द्वारा तय की जा सकती है) अगर और केवल अगर भाषा बूलियन सर्किट के एक समान परिवार द्वारा तय की जाती है।

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

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

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

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

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

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

इतिहास

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

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

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

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

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

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

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

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

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

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

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

जटिलता वर्ग

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

[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-14] 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-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.

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

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

[Carmosino-Impagliazzo-Kabanets-Kolokolova_2016-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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

@@ Line 14: / Line 14: @@
 ये धारणाएं सामान्यीकृत होती हैं जब कोई किसी भाषा की परिपथ जटिलता पर विचार करता है जिसमें अलग-अलग बिट लंबाई वाले तार होते हैं, विशेष रूप से अनंत [[औपचारिक भाषा]]एं। यद्यपि, बूलियन परिपथ केवल निश्चित संख्या में इनपुट बिट्स की अनुमति देते हैं। इस प्रकार, कोई एकल बूलियन परिपथ ऐसी भाषा तय करने में सक्षम नहीं है। इस संभावना को ध्यान में रखते हुए, परिपथ के वर्गों पर विचार किया जाता है <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>. परिपथ-डेप्थ जटिलता को इसी तरह परिभाषित किया गया है।
 == एकरूपता ==
@@ Line 23: / Line 23: @@
 * एम बहुपद समय में चलता है
 * सभी के लिए <math>n \in \mathbb{N}</math>, M का विवरण आउटपुट करता है <math>C_n</math> इनपुट पर <math>1^n</math>
 === लॉगस्थान समरूप ===
@@ Line 29: / Line 28: @@
 * M लघुगणकीय स्थान में चलता है
 * सभी के लिए <math>n \in \mathbb{N}</math>, M का विवरण आउटपुट करता है <math>C_n</math> इनपुट पर <math>1^n</math>
 == इतिहास ==
 में परिपथ जटिलता [[क्लाउड शैनन]] के पास वापस जाती है,<ref name="Shannon_1949"/> जिन्होंने सिद्ध किया कि n चरों पर लगभग सभी बूलियन कार्यों के लिए आकार Θ(2n/n) के परिपथों की आवश्यकता होती है. इस तथ्य के अतिरिक्त, जटिलता सिद्धांतवादी अब तक किसी भी स्पष्ट कार्य के लिए सुपरलीनियर निम्न परिबंध सिद्ध करने में असमर्थ रहे हैं।
@@ Line 36: / Line 33: @@
 उपयोग किए गए परिपथ के वर्ग पर कुछ प्रतिबंधों के अनुसार अधिबहुपद निचली सीमाएं सिद्ध हुई हैं। पहला कार्य जिसके लिए अधिबहुपद परिपथ निचली सीमाएँ दिखाई गई थीं, समता फलन था, जो इसके इनपुट बिट्स मॉड्यूलो 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>.
+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>.
 में, [[घाव एक बार|घाव बार]] और [[पियरे मैकेंजी]] ने बाद में दिखाया कि मोनोटोन एनसी पदानुक्रम अनंत है।<ref name="Raz-McKenzie_1999"/>
-पूर्णांक विभाजन समस्या एकसमान TC0|TC TC<sup>0</sup> में निहित है<sup>0।<ref name="Hesse_2001"/>
+पूर्णांक विभाजन समस्या एकसमान TC0|TC TC<sup>0</sup> में निहित है<sup>।<ref name="Hesse_2001"/>
 == परिपथ निचली सीमा ==
@@ Line 51: / Line 47: @@
 यह खुला है कि क्या नेक्स्पटाइम के पास असमान TC<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"/>
-में, रज़बोरोव और रुडिच ने दिखाया कि स्पष्ट बूलियन कार्यों के लिए कई ज्ञात परिपथ निचली सीमाएं संबंधित परिपथ वर्ग के विरुद्ध तथाकथित [[प्राकृतिक प्रमाण]] के अस्तित्व का संकेत देती हैं।<ref name="Razborov-Rudich_1997"/> दूसरी ओर, पी/पॉली के खिलाफ उपयोगी प्राकृतिक गुण शक्तिशाली छद्म यादृच्छिक जनरेटर को तोड़ देंगे। इसे अधिकांशतः शक्तिशाली परिपथ निचली सीमा सिद्ध करने के लिए प्राकृतिक सबूत बाधा के रूप में व्याख्या की जाती है। 2016 में, कारमोसिनो, इम्पैग्लियाज़ो, कबनेट्स और कोलोकोलोवा ने सिद्ध कर दिया कि कुशल शिक्षण एल्गोरिदम के निर्माण के लिए प्राकृतिक गुणों का भी उपयोग किया जा सकता है।<ref name="Carmosino-Impagliazzo-Kabanets-Kolokolova_2016"/>
+में, रज़बोरोव और रुडिच ने दिखाया कि स्पष्ट बूलियन कार्यों के लिए कई ज्ञात परिपथ निचली सीमाएं संबंधित परिपथ वर्ग के विरुद्ध तथाकथित [[प्राकृतिक प्रमाण]] के अस्तित्व का संकेत देती हैं।<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 गेट्स का उपयोग करना। इन सभी वर्गों की संघ एनसी चर्चा का विषय है। असीमित फैन-इन गेट्स पर विचार करके, कक्षाएं 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>
 == यह भी देखें ==
 * [[सर्किट न्यूनीकरण|परिपथ न्यूनीकरण]]
@@ Line 71: / Line 63: @@
 <ref group="nb" name="NB1">See [[Karp-Lipton theorem#Application for circuit lower bounds - Kannan's theorem|proof]].</ref>
 }}
 ==संदर्भ==
@@ Line 94: / 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>
 }}
 ==अग्रिम पठन==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 14:36, 3 March 2023

Contents

आकार और गहराई

एकरूपता

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

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

इतिहास

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

जटिलता वर्ग

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

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 14:36, 3 March 2023

आकार और गहराई

एकरूपता

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

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

इतिहास

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

जटिलता वर्ग

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

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories