अंकगणितीय परिपथ सम्मिश्रता: Difference between revisions

Latest revision as of 09:24, 12 June 2023

कम्प्यूटेशनल जटिलता सिद्धांत में, अंकगणितीय परिपथ बहुपदों की गणना के लिए मानक मॉडल हैं। अनौपचारिक रूप से, एक अंकगणितीय परिपथ इनपुट के रूप में या तो चर या संख्या लेता है, और इसे पहले से ही गणना की गई दो अभिव्यक्तियों को जोड़ने या गुणा करने की अनुमति है। अंकगणितीय परिपथ कंप्यूटिंग बहुपदों की जटिलता को समझने का एक औपचारिक तरीका प्रदान करते हैं। शोध की इस पंक्ति में मूल प्रकार का प्रश्न यह है कि किसी दिए गए बहुपद की गणना करने का सबसे कुशल तरीका क्या है?

परिभाषाएँ

एक साधारण अंकगणितीय सर्किट।

एक अंकगणितीय परिपथ $C$ क्षेत्र के ऊपर (गणित) $F$ और चर का सेट $x_{1},\ldots ,x_{n}$ इस प्रकार एक निर्देशित अचक्रिय ग्राफ है। इसमें प्रत्येक नोड को अंतःकोटि शून्य के साथ एक इनपुट फाटक कहा जाता है और इसे एक चर $x_{i}$ या एक क्षेत्र तत्व में $F.$ द्वारा लेबल किया जाता है। हर दूसरे फाटक को $+$ या $\times ;$ द्वारा लेबल किया जाता है पहली स्थिति में यह योग द्वार है और दूसरी स्थिति में गुणन द्वार है। एक अंकगणितीय सूत्र एक परिपथ है जिसमें प्रत्येक द्वार एक से आगे निकल जाता है (और इसलिए अंतर्निहित ग्राफ एक निर्देशित पेड़ है)।

एक परिपथ के साथ जटिलता के दो माप जुड़े होते हैं: आकार और गहराई। एक परिपथका आकार उसमें फाटकों की संख्या है, और एक परिपथ की गहराई उसमें सबसे लंबे निर्देशित पथ की लंबाई है। उदाहरण के लिए, आकृति में परिपथका आकार छह और गहराई दो है।

एक अंकगणितीय परिपथ निम्नलिखित प्राकृतिक तरीके से एक बहुपद की गणना करता है। एक इनपुट फाटक उस बहुपद की गणना करता है जिसके द्वारा इसे लेबल किया जाता है। एक योग द्वार $v$ अपने बच्चों द्वारा गणना किए गए बहुपदों के योग की गणना करता है (एक फाटक $u$ का $v$ बच्चा है यदि निर्देशित किनारा $(v,u)$ ग्राफ में है)। एक गुणन फाटक अपने बच्चों द्वारा गणना की गई बहुपदों के गुणन की गणना करता है। चित्र में परिपथपर विचार करें, उदाहरण के लिए: इनपुट फाटक गणना (बाएं से दाएं) $x_{1},x_{2}$ और $1,$ योग फाटक गणना $x_{1}+x_{2}$ और $x_{2}+1,$ और गुणन फाटक $(x_{1}+x_{2})x_{2}(x_{2}+1).$ गणना करता है।

अवलोकन

एक दिया गया बहुपद $f,$ हम अपने आप से पूछ सकते हैं कि इसकी गणना करने का सबसे अच्छा तरीका क्या है - उदाहरण के लिए, परिपथ कंप्यूटिंग $f.$ का सबसे छोटा आकार क्या है ,इस प्रश्न के उत्तर में दो भाग होते हैं। पहला भाग गणना $f;$ करने वाले कुछ परिपथ ढूंढ रहा है इस हिस्से को सामान्यतः $f.$ की ऊपरी सीमा की जटिलता कहा जाता है।दूसरा भाग दिखा रहा है कि कोई अन्य परिपथ अधिक अच्छा नहीं कर सकता; इस हिस्से को $f.$ की 'निचली सीमा' जटिलता कहा जाता है।यद्यपि ये दो कार्य दृढ़ता से संबंधित हैं, निचली सीमा को साबित करना सामान्यतः कठिन होता है, क्योंकि निचली सीमा को साबित करने के लिए एक ही समय में सभी परिपथो के बारे में बहस करने की आवश्यकता होती है।

ध्यान दें कि हम बहुपदों को परिभाषित करने वाले कार्यों के अतिरिक्त बहुपदों की औपचारिक गणना में रुचि रखते हैं। उदाहरण के लिए, बहुपद $x^{2}+x;$ पर विचार करें,दो तत्वों के क्षेत्र में यह बहुपद शून्य कार्य का प्रतिनिधित्व करता है, लेकिन यह शून्य बहुपद नहीं है। यह अंकगणितीय परिपथों के अध्ययन और बूलियन परिपथों के अध्ययन के बीच के अंतरों में से एक है। बूलियन जटिलता में, किसी को इसके कुछ प्रतिनिधित्व (हमारे कारक में, एक बहुपद द्वारा प्रतिनिधित्व) के अतिरिक्त किसी फलन की गणना करने में अधिक रुचि होती है। यह उन कारणों में से एक है जो बूलियन जटिलता को अंकगणितीय जटिलता से कठिन बनाते हैं। अंकगणितीय परिपथों के अध्ययन को भी बूलियन कारक केअध्ययन की दिशा में मध्यवर्ती चरणों में से एक माना जा सकता है,^[1] जिसे हम कम ही समझ पाते हैं।

ऊपरी सीमा

कंप्यूटिंग बहुपदों की जटिलता के अध्ययन के भाग के रूप में, कुछ चालाक परिपथ (वैकल्पिक रूप से एल्गोरिदम) पाए गए। मैट्रिक्स गुणन के लिए स्ट्रैसेन का एल्गोरिदम एक प्रसिद्ध उदाहरण है। दो के $n\times n$ गुणन की गणना करने का सीधा तरीका $n^{3}.$ मेट्रिसेस को आकार क्रम के एक परिपथ की आवश्यकता होती है। स्ट्रैसन ने दिखाया कि वास्तव में, हम लगभग $n^{2.807}.$ आकार के परिपथ का उपयोग करके दो आव्यूहों को गुणा कर सकते हैं।स्ट्रैसन का मूल विचार $2\times 2$ का गुणा करने का एक चतुर तरीका मैट्रिक्स है।यह विचार मैट्रिक्स गुणन की कम्प्यूटेशनल जटिलता का प्रारंभिक बिंदु है जिसमें लगभग $n^{2.376}.$ समय लगता है।

एक $n\times n$ आव्यूह के निर्धारक की गणना के पीछे एक और रोचक कहानी है। निर्धारक की गणना करने के सरल तरीके के लिए लगभग $n!.$ आकार के परिपथ की आवश्यकता होती है तथापि, हम जानते हैं कि आकार बहुपद $n$ के निर्धारक की गणना के लिए परिपथ होते हैं। यद्यपि, इन परिपथो में गहराई होती है जो $n.$ में रैखिक होती है बर्कोविट्ज़ एक सुधार के साथ आए: $n$ में बहुपद आकार का एक परिपथ लेकिन $O(\log ^{2}(n)).$ गहराई का। ^[2]

हम एक $n\times n$ आव्यूह के स्थायी (गणित) के लिए ज्ञात सर्वोत्तम परिपथ का भी उल्लेख करना चाहेंगे । निर्धारक के रूप में, स्थायी के लिए सरल परिपथ का आकार लगभग $n!.$ होता है। यद्यपि, स्थायी रूप से ज्ञात सर्वश्रेष्ठ परिपथ का आकार लगभग $2^{n},$ होता है जो रायसर के सूत्र द्वारा दिया गया है: एक $n\times n$ आव्यूह के लिए $X=(x_{i,j}),$

\operatorname {perm} (X)=(-1)^{n}\sum _{S\subseteq \{1,\ldots ,n\}}(-1)^{|S|}\prod _{i=1}^{n}\sum _{j\in S}x_{i,j}

(यह एक गहराई तीन परिपथ है)।

निचली सीमाएं

निचली सीमा सिद्ध करने के कारक में, हमारा ज्ञान बहुत सीमित है। चूंकि हम औपचारिक बहुपदों की गणना का अध्ययन करते हैं, हम जानते हैं कि बहुत बड़ी कोटि के बहुपदों के लिए बड़े परिपथों की आवश्यकता होती है, उदाहरण के लिए, $2^{2^{n}}$ कोटि के बहुपद को लगभग $2^{n}.$ आकार के एक परिपथ की आवश्यकता होती है इसलिए, छोटी कोटि के बहुपदों के लिए निचली बाध्यता साबित करना का मुख्य लक्ष्य, बहुपद में $n.$ है।वास्तव में, जैसा कि गणित के कई क्षेत्रों में होता है, गिनती के तर्क हमें बताते हैं कि बहुपद कोटि के बहुपद हैं जिनके लिए सुपरबहुपद आकार के परिपथ की आवश्यकता होती है। यद्यपि, ये गिनती के तर्क सामान्यतः गणना की हमारी समझ में सुधार नहीं करते हैं। अनुसंधान के इस क्षेत्र में निम्नलिखित समस्या मुख्य खुली समस्या है: बहुपद कोटि का एक 'स्पष्ट' बहुपद खोजें जिसके लिए सुपरबहुपद आकार के परिपथ की आवश्यकता होती है।

कला की अवस्था एक $\Omega (n\log d)$ है एक परिपथ के आकार के लिए निचली सीमा अभिकलन कर रहा है,, उदाहरण के लिए, बहुपद $x_{1}^{d}+\cdots +x_{n}^{d}$ वोल्कर स्ट्रास और बाउर और स्ट्रैसन द्वारा दिया गया। अधिक सटीक रूप से, स्ट्रैसन ने बेज़ाउट लेम्मा का उपयोग यह दिखाने के लिए किया कि कोई भी परिपथ जो एक साथ $n$ बहुआयामी पद $x_{1}^{d},\ldots ,x_{n}^{d}$ की गणना करता है $\Omega (n\log d),$ आकार का है और बाद में बाउर और स्ट्रैसन ने निम्नलिखित दिखाया: कोई अधिक से अधिक $O(s)$ आकार का एक नया परिपथ बना सकता है जो $f$ और $f.$ के सभी $n$ आंशिक व्युत्पन्न की गणना करता है।उपरान्त $x_{1}^{d}+\cdots +x_{n}^{d}$ के आंशिक व्युत्पन्न $dx_{1}^{d-1},\ldots ,dx_{n}^{d-1},$ हैं स्ट्रैसन की निचली सीमा $x_{1}^{d}+\cdots +x_{n}^{d}$ भी में लागू होती है । यह एक उदाहरण है जहां कुछ ऊपरी सीमा निचली सीमा को साबित करने में मदद करती है; बाउर और स्ट्रैसन द्वारा दिए गए परिपथ के निर्माण से अधिक सामान्य बहुपदों के लिए एक निचली सीमा का पता चलता है।

निचली सीमाओं को साबित करने की क्षमता की कमी हमें संगणना के सरल मॉडल पर विचार करने के लिए प्रेरित करती है। कुछ उदाहरण हैं: एकदिष्ट परिपथ(जिसमें सभी क्षेत्र तत्व गैर-ऋणात्मक वास्तविक संख्याएं हैं), निरंतर गहराई वाले सर्किट, और बहुरैखिक परिपथ(जिसमें हर फाटक एक बहुरेखीय बहुपद की गणना करता है)। इन प्रतिबंधित मॉडलों का बड़े पैमाने पर अध्ययन किया गया है और कुछ समझ और परिणाम प्राप्त हुए हैं।

बीजगणितीय पी और एनपी

कम्प्यूटेशनल जटिलता सिद्धांत में सबसे रोचकखुली समस्या P विरुद्ध NP समस्या है। लगभग, यह समस्या यह निर्धारित करने के लिए है कि क्या दी गई समस्या को उतनी ही आसानी से हल किया जा सकता है, जितनी आसानी से यह दिखाया जा सकता है कि दी गई समस्या का समाधान उपस्थित है। अपने बीजीय कार्य उपस्थिति में^[3] इस समस्या के एक बीजीय अनुरूप का सुझाव दिया, VP विरुद्ध VNP समस्या है।

कक्षाVP ,P का बीजगणितीय अनुरूप है; यह बहुपदों $f$ का वर्ग है बहुपद की कोटि जिसमें एक निश्चित क्षेत्र पर $K.$ बहुपद आकार के परिपथ होते हैं।वीएनपी वर्ग एनपी का एनालॉग है। VNP को बहुपदों $f$ के बहुपद कोटि के वर्ग के रूप में माना जा सकता है जैसे कि एक एकपद दिए जाने पर हम इसके गुणांक $f$ को कुशलतापूर्वक, एक बहुपद आकार परिपथ के साथ निर्धारित कर सकते हैं।

जटिलता सिद्धांत में बुनियादी धारणाओं में से एक पूर्णता की धारणा है। बहुपदों के एक वर्ग (जैसे VP या VNP) को देखते हुए, एक पूर्ण बहुपद $f$ इस वर्ग के लिए दो गुणों वाला एक बहुपद है: (1) यह वर्ग का हिस्सा है, और (2) कोई अन्य बहुपद $g$ की तुलना में कक्षा $f,$ में आसान है इस अर्थ में कि यदि $f$ एक छोटा परिपथ है तो ऐसा $g.$ करता है। वैलेंट ने दिखाया कि VNP वर्ग के लिए स्थायी पूर्ण है। इसलिये यह दिखाने के लिए किVP, VNP के बराबर नहीं है, किसी को यह दिखाने की जरूरत है कि स्थायी में बहुपद आकार के परिपथ नहीं होते हैं। यह एक उत्कृष्ट खुली समस्या बनी हुई है।

गहराई में कमी

बहुपदों की गणना की हमारी समझ में एक मानदण्ड वैलिएंट, स्काईम, बर्कोविट्ज और रैकॉफ का काम है।^[4] उन्होंने दिखाया कि यदि एक बहुपद $f$ कोटि $r$ का आकार $s,$ का एक परिपथ है तब बहुपद $f$ में $r$ और $s$ आकार का $O(\log(r)\log(s)).$ गहराई का एक परिपथ भी है।उदाहरण के लिए, $n$ कोटि का कोई बहुपद जिसमें बहुपद आकार का परिपथ होता है, लगभग $\log ^{2}(n).$ गहराई का बहुपद आकार परिपथ भी होता है यह परिणाम बर्कोविट्ज़ के परिपथ को बहुपद कोटि के किसी भी बहुपद के लिए सामान्यीकृत करता है जिसमें बहुपद आकार परिपथ(जैसे निर्धारक) होता है। बूलियन व्यवस्थान में इस परिणाम का एनालॉग गलत माना जाता है।

इस परिणाम का एक परिणाम अपेक्षाकृत छोटे सूत्रों द्वारा परिपथों का अनुकरण है, अर्धबहुपद आकार के सूत्र: यदि एक बहुपद $f$ , $r$ कोटि का $s,$ आकार का एक परिपथ है तो इसके आकार का एक सूत्र है $s^{O(\log(r))}.$ यह अनुकरण वैलियन्ट अल अल की गहराई में कमी से आसान है और पहले हयाफिल द्वारा दिखाया गया था।^[5]

यह भी देखें

बहुपद मूल्यांकन की जटिलता की अधिक सामान्य और कम औपचारिक चर्चा के लिए बहुपद मूल्यांकन।

अग्रिम पठन

Bürgisser, Peter (2000). Completeness and reduction in algebraic complexity theory. Algorithms and Computation in Mathematics. Vol. 7. Berlin: Springer-Verlag. ISBN 978-3-540-66752-0. Zbl 0948.68082.
Bürgisser, Peter; Clausen, Michael; Shokrollahi, M. Amin (1997). Algebraic complexity theory. Grundlehren der Mathematischen Wissenschaften. Vol. 315. With the collaboration of Thomas Lickteig. Berlin: Springer-Verlag. ISBN 978-3-540-60582-9. Zbl 1087.68568.
von zur Gathen, Joachim (1988). "Algebraic complexity theory". Annual Review of Computer Science. 3: 317–347. doi:10.1146/annurev.cs.03.060188.001533.

फुटनोट्स

↑ L. G. Valiant. Why is Boolean complexity theory difficult? Proceedings of the London Mathematical Society symposium on Boolean function complexity, pp. 84–94, 1992.
↑ S. J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Inf. Prod. Letters 18, pp. 147–150, 1984.
↑ L. G. Valiant. Completeness classes in algebra. In Proc. of 11th ACM STOC, pp. 249–261, 1979.
↑ L. G. Valiant, S. Skyum, S. Berkowitz, C. Rackoff. Fast parallel computation of polynomials using few processors. SIAM J. Comput. 12(4), pp. 641–644, 1983.
↑ L. Hyafil. On the parallel evaluation of multivariate polynomials. SIAM J. Comput. 8(2), pp. 120–123, 1979.

श्रेणी:सर्किट जटिलता

[1] L. G. Valiant. Why is Boolean complexity theory difficult? Proceedings of the London Mathematical Society symposium on Boolean function complexity, pp. 84–94, 1992.

[2] S. J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Inf. Prod. Letters 18, pp. 147–150, 1984.

[3] L. G. Valiant. Completeness classes in algebra. In Proc. of 11th ACM STOC, pp. 249–261, 1979.

[4] L. G. Valiant, S. Skyum, S. Berkowitz, C. Rackoff. Fast parallel computation of polynomials using few processors. SIAM J. Comput. 12(4), pp. 641–644, 1983.

[5] L. Hyafil. On the parallel evaluation of multivariate polynomials. SIAM J. Comput. 8(2), pp. 120–123, 1979.

[1]

[2]

[3]

[4]

[5]

@@ Line 1: / Line 1: @@
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, अंकगणितीय सर्किट बहुपदों की गणना के लिए मानक मॉडल हैं। अनौपचारिक रूप से, एक अंकगणितीय सर्किट इनपुट के रूप में या तो चर या संख्या लेता है, और इसे पहले से ही गणना की गई दो अभिव्यक्तियों को जोड़ने या गुणा करने की अनुमति है। अंकगणितीय सर्किट कंप्यूटिंग बहुपदों की जटिलता को समझने का एक औपचारिक तरीका प्रदान करते हैं। शोध की इस पंक्ति में मूल प्रकार का प्रश्न यह है कि किसी दिए गए बहुपद की गणना करने का सबसे कुशल तरीका क्या है <math>f</math>?
+[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, अंकगणितीय परिपथ बहुपदों की गणना के लिए मानक मॉडल हैं। अनौपचारिक रूप से, एक अंकगणितीय परिपथ इनपुट के रूप में या तो चर या संख्या लेता है, और इसे पहले से ही गणना की गई दो अभिव्यक्तियों को जोड़ने या गुणा करने की अनुमति है। अंकगणितीय परिपथ कंप्यूटिंग बहुपदों की जटिलता को समझने का एक औपचारिक तरीका प्रदान करते हैं। शोध की इस पंक्ति में मूल प्रकार का प्रश्न यह है कि किसी दिए गए बहुपद की गणना करने का सबसे कुशल तरीका क्या है?
 == परिभाषाएँ ==
-[[Image:ArithmeticCircuit.svg|right|frame|एक साधारण अंकगणितीय सर्किट।]]एक अंकगणितीय सर्किट <math>C</math> क्षेत्र के ऊपर (गणित) <math>F</math> और चर का सेट <math>x_1, \ldots, x_n</math> इस प्रकार एक निर्देशित विश्वकोश ग्राफ है। इसमें प्रत्येक नोड को इं[[डिग्री]] शून्य के साथ एक इनपुट गेट कहा जाता है और इसे एक चर द्वारा लेबल किया जाता है <math>x_i</math> या एक क्षेत्र तत्व में <math>F.</math> हर दूसरे गेट को या तो लेबल किया जाता है <math>+</math> या <math>\times;</math> पहली स्थिति में यह योग द्वार है और दूसरी स्थिति में उत्पाद द्वार है। एक अंकगणितीय सूत्र एक सर्किट है जिसमें प्रत्येक द्वार एक से आगे निकल जाता है (और इसलिए अंतर्निहित ग्राफ एक [[निर्देशित पेड़]] है)।
+[[Image:ArithmeticCircuit.svg|right|frame|एक साधारण अंकगणितीय सर्किट।]]एक अंकगणितीय परिपथ <math>C</math> क्षेत्र के ऊपर (गणित) <math>F</math> और चर का सेट <math>x_1, \ldots, x_n</math> इस प्रकार एक निर्देशित अचक्रिय ग्राफ है। इसमें प्रत्येक नोड को अंतःकोटि शून्य के साथ एक इनपुट फाटक कहा जाता है और इसे एक चर <math>x_i</math>या एक क्षेत्र तत्व में <math>F.</math>द्वारा लेबल किया जाता है।  हर दूसरे फाटक को  <math>+</math> या <math>\times;</math> द्वारा लेबल किया जाता है पहली स्थिति में यह योग द्वार है और दूसरी स्थिति में गुणन द्वार है। एक अंकगणितीय सूत्र एक परिपथ है जिसमें प्रत्येक द्वार एक से आगे निकल जाता है (और इसलिए अंतर्निहित ग्राफ एक [[निर्देशित पेड़]] है)।
-एक परिपथ के साथ जटिलता के दो माप जुड़े होते हैं: आकार और गहराई। एक सर्किट का आकार उसमें फाटकों की संख्या है, और एक सर्किट की गहराई उसमें सबसे लंबे निर्देशित पथ की लंबाई है। उदाहरण के लिए, आकृति में सर्किट का आकार छह और गहराई दो है।
+एक परिपथ के साथ जटिलता के दो माप जुड़े होते हैं: आकार और गहराई। एक परिपथका आकार उसमें फाटकों की संख्या है, और एक परिपथ की गहराई उसमें सबसे लंबे निर्देशित पथ की लंबाई है। उदाहरण के लिए, आकृति में परिपथका आकार छह और गहराई दो है।
-एक अंकगणितीय सर्किट निम्नलिखित प्राकृतिक तरीके से एक बहुपद की गणना करता है। एक इनपुट गेट उस बहुपद की गणना करता है जिसके द्वारा इसे लेबल किया जाता है। एक योग द्वार <math>v</math> अपने बच्चों द्वारा गणना किए गए बहुपदों के योग की गणना करता है (एक गेट <math>u</math> का बच्चा है <math>v</math> यदि निर्देशित किनारा <math>(v,u)</math> ग्राफ में है)। एक उत्पाद गेट अपने बच्चों द्वारा गणना की गई बहुपदों के उत्पाद की गणना करता है। चित्र में सर्किट पर विचार करें, उदाहरण के लिए: इनपुट गेट्स गणना (बाएं से दाएं) <math>x_1, x_2</math> और <math>1,</math> योग गेट्स गणना <math>x_1 + x_2</math> और <math>x_2 + 1,</math> और उत्पाद गेट गणना करता है <math>(x_1 + x_2) x_2 (x_2 +1).</math>
+एक अंकगणितीय परिपथ निम्नलिखित प्राकृतिक तरीके से एक बहुपद की गणना करता है। एक इनपुट फाटक उस बहुपद की गणना करता है जिसके द्वारा इसे लेबल किया जाता है। एक योग द्वार <math>v</math> अपने बच्चों द्वारा गणना किए गए बहुपदों के योग की गणना करता है (एक फाटक <math>u</math> का <math>v</math> बच्चा है यदि निर्देशित किनारा <math>(v,u)</math> ग्राफ में है)। एक गुणन फाटक अपने बच्चों द्वारा गणना की गई बहुपदों के गुणन की गणना करता है। चित्र में परिपथपर विचार करें, उदाहरण के लिए: इनपुट फाटक गणना (बाएं से दाएं) <math>x_1, x_2</math> और <math>1,</math> योग फाटक गणना <math>x_1 + x_2</math> और <math>x_2 + 1,</math> और गुणन फाटक <math>(x_1 + x_2) x_2 (x_2 +1).</math>गणना करता है।
+== अवलोकन ==
+एक दिया गया बहुपद <math>f,</math> हम अपने आप से पूछ सकते हैं कि इसकी गणना करने का सबसे अच्छा तरीका क्या है - उदाहरण के लिए, परिपथ कंप्यूटिंग <math>f.</math> का सबसे छोटा आकार क्या है ,इस प्रश्न के उत्तर में दो भाग होते हैं। पहला भाग गणना<math>f;</math> करने वाले कुछ परिपथ ढूंढ रहा है  इस हिस्से को सामान्यतः<math>f.</math> की ऊपरी सीमा की जटिलता कहा जाता है।दूसरा भाग दिखा रहा है कि कोई अन्य परिपथ अधिक अच्छा नहीं कर सकता; इस हिस्से को <math>f.</math>की 'निचली सीमा' जटिलता कहा जाता है।यद्यपि ये दो कार्य दृढ़ता से संबंधित हैं, निचली सीमा को साबित करना सामान्यतः कठिन होता है, क्योंकि निचली सीमा को साबित करने के लिए एक ही समय में सभी परिपथो के बारे में बहस करने की आवश्यकता होती है।
+ध्यान दें कि हम बहुपदों को परिभाषित करने वाले कार्यों के अतिरिक्त बहुपदों की औपचारिक गणना में रुचि रखते हैं। उदाहरण के लिए, बहुपद <math>x^2 +x;</math> पर विचार करें,दो तत्वों के क्षेत्र में यह बहुपद शून्य कार्य का प्रतिनिधित्व करता है, लेकिन यह शून्य बहुपद नहीं है। यह अंकगणितीय परिपथों के अध्ययन और बूलियन परिपथों के अध्ययन के बीच के अंतरों में से एक है। बूलियन जटिलता में, किसी को इसके कुछ प्रतिनिधित्व (हमारे कारक में, एक बहुपद द्वारा प्रतिनिधित्व) के अतिरिक्त किसी फलन की गणना करने में अधिक रुचि होती है। यह उन कारणों में से एक है जो बूलियन जटिलता को अंकगणितीय जटिलता से कठिन बनाते हैं। अंकगणितीय परिपथों के अध्ययन को भी बूलियन कारक केअध्ययन की दिशा में मध्यवर्ती चरणों में से एक माना जा सकता है,<ref>L. G. Valiant. ''Why is Boolean complexity theory difficult?'' Proceedings of the London Mathematical Society symposium on Boolean function complexity, pp. 84–94, 1992.</ref> जिसे हम कम ही समझ पाते हैं।
-== सिंहावलोकन ==
+=== ऊपरी सीमा ===
-एक बहुपद दिया <math>f,</math> हम अपने आप से पूछ सकते हैं कि इसकी गणना करने का सबसे अच्छा तरीका क्या है - उदाहरण के लिए, सर्किट कंप्यूटिंग का सबसे छोटा आकार क्या है <math>f.</math> इस प्रश्न के उत्तर में दो भाग होते हैं। पहला भाग गणना करने वाले कुछ सर्किट ढूंढ रहा है <math>f;</math> इस हिस्से को आमतौर पर ऊपरी सीमा की जटिलता कहा जाता है <math>f.</math> दूसरा भाग दिखा रहा है कि कोई अन्य सर्किट बेहतर नहीं कर सकता; इस हिस्से को 'लोअर बाउंडिंग' की जटिलता कहा जाता है  <math>f.</math> हालांकि ये दो कार्य दृढ़ता से संबंधित हैं, निचली सीमा को साबित करना आमतौर पर कठिन होता है, क्योंकि निचली सीमा को साबित करने के लिए एक ही समय में सभी सर्किटों के बारे में बहस करने की आवश्यकता होती है।
+कंप्यूटिंग बहुपदों की जटिलता के अध्ययन के भाग के रूप में, कुछ चालाक परिपथ (वैकल्पिक रूप से एल्गोरिदम) पाए गए। [[मैट्रिक्स उत्पाद|मैट्रिक्स गुणन]] के लिए स्ट्रैसेन का एल्गोरिदम एक प्रसिद्ध उदाहरण है। दो के<math>n \times n </math> गुणन की गणना करने का सीधा तरीका <math>n^3.</math> मेट्रिसेस को आकार क्रम के एक परिपथ की आवश्यकता होती है। स्ट्रैसन ने दिखाया कि वास्तव में, हम लगभग <math>n^{2.807}.</math>आकार के परिपथ का उपयोग करके दो आव्यूहों को गुणा कर सकते हैं।स्ट्रैसन का मूल विचार <math>2 \times 2 </math> का गुणा करने का एक चतुर तरीका मैट्रिक्स है।यह विचार [[मैट्रिक्स गुणन की कम्प्यूटेशनल जटिलता]] का प्रारंभिक बिंदु है जिसमें लगभग <math>n^{2.376}.</math>समय लगता है।
-ध्यान दें कि हम बहुपदों को परिभाषित करने वाले कार्यों के बजाय बहुपदों की औपचारिक गणना में रुचि रखते हैं। उदाहरण के लिए, बहुपद पर विचार करें <math>x^2 +x;</math> दो तत्वों के क्षेत्र में यह बहुपद शून्य कार्य का प्रतिनिधित्व करता है, लेकिन यह शून्य बहुपद नहीं है। यह अंकगणितीय परिपथों के अध्ययन और बूलियन परिपथों के अध्ययन के बीच के अंतरों में से एक है। बूलियन जटिलता में, किसी को इसके कुछ प्रतिनिधित्व (हमारे मामले में, एक बहुपद द्वारा प्रतिनिधित्व) के बजाय किसी फ़ंक्शन की गणना करने में अधिक रुचि होती है। यह उन कारणों में से एक है जो बूलियन जटिलता को अंकगणितीय जटिलता से कठिन बनाते हैं। अंकगणितीय परिपथों के अध्ययन को भी बूलियन मामले के अध्ययन की दिशा में मध्यवर्ती चरणों में से एक माना जा सकता है,<ref>L. G. Valiant. ''Why is Boolean complexity theory difficult?'' Proceedings of the London Mathematical Society symposium on Boolean function complexity, pp. 84–94, 1992.</ref> जिसे हम कम ही समझ पाते हैं।
+एक  <math>n \times n </math> आव्यूह के निर्धारक की गणना के पीछे एक और रोचक कहानी है। निर्धारक की गणना करने के सरल तरीके के लिए लगभग <math>n!.</math>आकार के परिपथ की आवश्यकता होती है   तथापि, हम जानते हैं कि आकार बहुपद <math>n</math> के निर्धारक की गणना के लिए परिपथ होते हैं। यद्यपि, इन परिपथो में गहराई होती है जो <math>n.</math>में रैखिक होती है  बर्कोविट्ज़ एक सुधार के साथ आए: <math>n</math> में बहुपद आकार का एक परिपथ लेकिन <math>O(\log^2(n)).</math> गहराई का। <ref>S. J. Berkowitz. ''On computing the determinant in small parallel time using a small number of processors.'' Inf. Prod. Letters 18, pp. 147–150, 1984.</ref>
-=== ऊपरी सीमा ===
+हम एक <math>n \times n </math> आव्यूह के [[स्थायी (गणित)]] के लिए ज्ञात सर्वोत्तम परिपथ का भी उल्लेख करना चाहेंगे  । निर्धारक के रूप में, स्थायी के लिए  सरल परिपथ का आकार लगभग <math>n!.</math>होता है।  यद्यपि, स्थायी रूप से ज्ञात सर्वश्रेष्ठ परिपथ का आकार लगभग <math>2^n,</math> होता है  जो रायसर के सूत्र द्वारा दिया गया है: एक <math>n \times n </math> आव्यूह के लिए  <math>X = (x_{i,j}),</math>
-कंप्यूटिंग बहुपदों की जटिलता के अध्ययन के भाग के रूप में, कुछ चालाक सर्किट (वैकल्पिक रूप से एल्गोरिदम) पाए गए। एक प्रसिद्ध उदाहरण है वोल्कर स्ट्रैसेन | [[मैट्रिक्स उत्पाद]] के लिए स्ट्रैसेन का एल्गोरिदम। दो के उत्पाद की गणना करने का सीधा तरीका <math>n \times n </math> मेट्रिसेस को आकार क्रम के एक सर्किट की आवश्यकता होती है <math>n^3.</math> स्ट्रैसन ने दिखाया कि वास्तव में, हम मोटे तौर पर आकार के सर्किट का उपयोग करके दो आव्यूहों को गुणा कर सकते हैं <math>n^{2.807}.</math> स्ट्रैसन का मूल विचार गुणा करने का एक चतुर तरीका है <math>2 \times 2 </math> मैट्रिक्स। यह विचार [[मैट्रिक्स गुणन की कम्प्यूटेशनल जटिलता]] का प्रारंभिक बिंदु है जिसमें मोटे तौर पर समय लगता है <math>n^{2.376}.</math>
-एक के निर्धारक की गणना के पीछे एक और दिलचस्प कहानी है <math>n \times n </math> आव्यूह। निर्धारक की गणना करने के सरल तरीके के लिए मोटे तौर पर आकार के सर्किट की आवश्यकता होती है <math>n!.</math> फिर भी, हम जानते हैं कि आकार बहुपद के परिपथ होते हैं <math>n</math> निर्धारक की गणना के लिए। हालाँकि, इन सर्किटों में गहराई होती है जो रैखिक होती है <math>n.</math> बर्कोविट्ज़ एक सुधार के साथ आया: आकार बहुपद का एक सर्किट <math>n,</math> लेकिन गहराई का <math>O(\log^2(n)).</math><ref>S. J. Berkowitz. ''On computing the determinant in small parallel time using a small number of processors.'' Inf. Prod. Letters 18, pp. 147–150, 1984.</ref>
-हम एक के [[स्थायी (गणित)]] के लिए ज्ञात सर्वोत्तम परिपथ का भी उल्लेख करना चाहेंगे <math>n \times n </math> आव्यूह। निर्धारक के रूप में, स्थायी के लिए भोली सर्किट का आकार लगभग होता है <math>n!.</math> हालांकि, स्थायी रूप से ज्ञात सर्वश्रेष्ठ सर्किट का आकार मोटे तौर पर होता है <math>2^n,</math> जो रायसर के सूत्र द्वारा दिया गया है: एक के लिए <math>n \times n </math> आव्यूह <math>X = (x_{i,j}),</math>
 :<math> \operatorname{perm}(X)=(-1)^n\sum_{S \subseteq \{1,\ldots,n\}}(-1)^{|S|} \prod_{i=1}^n \sum_{j \in S} x_{i,j} </math>
-(यह एक गहराई तीन सर्किट है)।
+(यह एक गहराई तीन परिपथ है)।
 === निचली सीमाएं ===
-निचली सीमा सिद्ध करने के मामले में, हमारा ज्ञान बहुत सीमित है। चूंकि हम औपचारिक बहुपदों की गणना का अध्ययन करते हैं, हम जानते हैं कि बहुत बड़ी डिग्री के बहुपदों के लिए बड़े परिपथों की आवश्यकता होती है, उदाहरण के लिए, डिग्री का बहुपद <math>2^{2^n}</math> मोटे तौर पर आकार के एक सर्किट की आवश्यकता होती है <math>2^n.</math> तो, मुख्य लक्ष्य छोटी डिग्री के बहुपदों के लिए निचली बाध्यता साबित करना है, कहें, बहुपद में <math>n.</math> वास्तव में, जैसा कि गणित के कई क्षेत्रों में होता है, गिनती के तर्क हमें बताते हैं कि बहुपद डिग्री के बहुपद हैं जिनके लिए सुपरपोलिनोमियल आकार के सर्किट की आवश्यकता होती है। हालाँकि, ये गिनती के तर्क आमतौर पर गणना की हमारी समझ में सुधार नहीं करते हैं। अनुसंधान के इस क्षेत्र में निम्नलिखित समस्या मुख्य खुली समस्या है: बहुपद डिग्री का एक 'स्पष्ट' बहुपद खोजें जिसके लिए सुपरपोलिनोमियल आकार के सर्किट की आवश्यकता होती है।
+निचली सीमा सिद्ध करने के कारक में, हमारा ज्ञान बहुत सीमित है। चूंकि हम औपचारिक बहुपदों की गणना का अध्ययन करते हैं, हम जानते हैं कि बहुत बड़ी कोटि के बहुपदों के लिए बड़े परिपथों की आवश्यकता होती है, उदाहरण के लिए,<math>2^{2^n}</math>कोटि के बहुपद को लगभग <math>2^n.</math> आकार के एक परिपथ की आवश्यकता होती है इसलिए, छोटी कोटि के बहुपदों के लिए निचली बाध्यता साबित करना का  मुख्य लक्ष्य, बहुपद में <math>n.</math> है।वास्तव में, जैसा कि गणित के कई क्षेत्रों में होता है, गिनती के तर्क हमें बताते हैं कि बहुपद कोटि के बहुपद हैं जिनके लिए सुपरबहुपद आकार के परिपथ की आवश्यकता होती है। यद्यपि, ये गिनती के तर्क सामान्यतः गणना की हमारी समझ में सुधार नहीं करते हैं। अनुसंधान के इस क्षेत्र में निम्नलिखित समस्या मुख्य खुली समस्या है: बहुपद  कोटि का एक 'स्पष्ट' बहुपद खोजें जिसके लिए सुपरबहुपद आकार के परिपथ की आवश्यकता होती है।
-कला की स्थिति एक है <math>\Omega(n \log d)</math> एक सर्किट कंप्यूटिंग के आकार के लिए निचली सीमा, उदाहरण के लिए, बहुपद <math>x_1^d + \cdots + x_n^d</math> [[वोल्कर स्ट्रास]] और बाउर और स्ट्रैसन द्वारा दिया गया। अधिक सटीक रूप से, स्ट्रैसन ने बेज़ाउट लेम्मा का उपयोग यह दिखाने के लिए किया कि कोई भी सर्किट जो एक साथ गणना करता है <math>n</math> बहुआयामी पद <math>x_1^d, \ldots, x_n^d</math> आकार का है <math>\Omega(n \log d),</math> और बाद में बाउर और स्ट्रैसन ने निम्नलिखित दिखाया: आकार का एक अंकगणितीय सर्किट दिया <math>s</math> एक बहुपद की गणना <math>f,</math> कोई अधिक से अधिक आकार का एक नया परिपथ बना सकता है <math>O(s)</math> जो गणना करता है <math>f</math> और सभी <math>n</math> का आंशिक व्युत्पन्न <math>f.</math> के आंशिक डेरिवेटिव के बाद से <math>x_1^d + \cdots + x_n^d</math> हैं <math>dx_1^{d-1}, \ldots, dx_n^{d-1},</math> स्ट्रैसन की निचली सीमा लागू होती है <math>x_1^d + \cdots + x_n^d</math> भी। यह एक उदाहरण है जहां कुछ ऊपरी सीमा निचली सीमा को साबित करने में मदद करती है; बाउर और स्ट्रैसन द्वारा दिए गए सर्किट के निर्माण से अधिक सामान्य बहुपदों के लिए एक निचली सीमा का पता चलता है।
+कला की अवस्था एक<math>\Omega(n \log d)</math> है एक परिपथ के आकार के लिए निचली सीमा अभिकलन कर रहा है,, उदाहरण के लिए, बहुपद <math>x_1^d + \cdots + x_n^d</math> [[वोल्कर स्ट्रास]] और बाउर और स्ट्रैसन द्वारा दिया गया। अधिक सटीक रूप से, स्ट्रैसन ने बेज़ाउट लेम्मा का उपयोग यह दिखाने के लिए किया कि कोई भी परिपथ जो एक साथ  <math>n</math> बहुआयामी पद <math>x_1^d, \ldots, x_n^d</math> की गणना करता है <math>\Omega(n \log d),</math> आकार का है  और बाद में बाउर और स्ट्रैसन ने निम्नलिखित दिखाया: कोई अधिक से अधिक <math>O(s)</math> आकार का एक नया परिपथ बना सकता है  जो <math>f</math> और  <math>f.</math> के सभी <math>n</math> आंशिक व्युत्पन्न की गणना करता है।उपरान्त <math>x_1^d + \cdots + x_n^d</math> के आंशिक व्युत्पन्न <math>dx_1^{d-1}, \ldots, dx_n^{d-1},</math> हैं स्ट्रैसन की निचली सीमा <math>x_1^d + \cdots + x_n^d</math> भी में लागू होती है । यह एक उदाहरण है जहां कुछ ऊपरी सीमा निचली सीमा को साबित करने में मदद करती है; बाउर और स्ट्रैसन द्वारा दिए गए परिपथ के निर्माण से अधिक सामान्य बहुपदों के लिए एक निचली सीमा का पता चलता है।
-निचली सीमाओं को साबित करने की क्षमता की कमी हमें संगणना के सरल मॉडल पर विचार करने के लिए प्रेरित करती है। कुछ उदाहरण हैं: मोनोटोन सर्किट (जिसमें सभी क्षेत्र तत्व गैर-ऋणात्मक वास्तविक संख्याएं हैं), निरंतर गहराई वाले सर्किट, और मल्टीलाइनियर सर्किट (जिसमें हर गेट एक [[बहुरेखीय बहुपद]] की गणना करता है)। इन प्रतिबंधित मॉडलों का बड़े पैमाने पर अध्ययन किया गया है और कुछ समझ और परिणाम प्राप्त हुए हैं।
+निचली सीमाओं को साबित करने की क्षमता की कमी हमें संगणना के सरल मॉडल पर विचार करने के लिए प्रेरित करती है। कुछ उदाहरण हैं: एकदिष्ट परिपथ(जिसमें सभी क्षेत्र तत्व गैर-ऋणात्मक वास्तविक संख्याएं हैं), निरंतर गहराई वाले सर्किट, और बहुरैखिक परिपथ(जिसमें हर फाटक एक [[बहुरेखीय बहुपद]] की गणना करता है)। इन प्रतिबंधित मॉडलों का बड़े पैमाने पर अध्ययन किया गया है और कुछ समझ और परिणाम प्राप्त हुए हैं।
-== बीजीय पी और एनपी ==
+== बीजगणितीय पी और एनपी ==
-कम्प्यूटेशनल जटिलता सिद्धांत में सबसे दिलचस्प खुली समस्या P बनाम NP समस्या है। मोटे तौर पर, यह समस्या यह निर्धारित करने के लिए है कि क्या दी गई समस्या को उतनी ही आसानी से हल किया जा सकता है, जितनी आसानी से यह दिखाया जा सकता है कि दी गई समस्या का समाधान मौजूद है। अपने सेमिनल वर्क वैलेंट में<ref>L. G. Valiant. ''Completeness classes in algebra.'' In Proc. of 11th ACM STOC, pp. 249–261, 1979.</ref> इस समस्या के एक बीजीय अनुरूप का सुझाव दिया, VP बनाम VNP समस्या।
+कम्प्यूटेशनल जटिलता सिद्धांत में सबसे  रोचकखुली समस्या P विरुद्ध NP समस्या है। लगभग, यह समस्या यह निर्धारित करने के लिए है कि क्या दी गई समस्या को उतनी ही आसानी से हल किया जा सकता है, जितनी आसानी से यह दिखाया जा सकता है कि दी गई समस्या का समाधान उपस्थित है। अपने बीजीय कार्य उपस्थिति में<ref>L. G. Valiant. ''Completeness classes in algebra.'' In Proc. of 11th ACM STOC, pp. 249–261, 1979.</ref> इस समस्या के एक बीजीय अनुरूप का सुझाव दिया, VP विरुद्ध VNP समस्या है।
-कक्षा वीपी पी का बीजगणितीय अनुरूप है; यह बहुपदों का वर्ग है  <math>f</math> बहुपद की डिग्री जिसमें एक निश्चित क्षेत्र पर बहुपद आकार के सर्किट होते हैं <math>K.</math> वीएनपी वर्ग एनपी का एनालॉग है। VNP को बहुपदों के वर्ग के रूप में माना जा सकता है <math>f</math> बहुपद डिग्री की ऐसी है कि एक मोनोमियल दिए जाने पर हम इसके गुणांक को निर्धारित कर सकते हैं <math>f</math> कुशलतापूर्वक, एक बहुपद आकार सर्किट के साथ।
+कक्षाVP ,P का बीजगणितीय अनुरूप है; यह बहुपदों <math>f</math> का वर्ग है  बहुपद की  कोटि जिसमें एक निश्चित क्षेत्र पर <math>K.</math> बहुपद आकार के परिपथ होते हैं।वीएनपी वर्ग एनपी का एनालॉग है। VNP को बहुपदों <math>f</math> के बहुपद  कोटि  के वर्ग के रूप में माना जा सकता है जैसे कि एक एकपद दिए जाने पर हम इसके गुणांक <math>f</math> को   कुशलतापूर्वक, एक बहुपद आकार परिपथ के साथ निर्धारित कर सकते हैं।
-जटिलता सिद्धांत में बुनियादी धारणाओं में से एक पूर्णता की धारणा है। बहुपदों के एक वर्ग (जैसे वीपी या वीएनपी) को देखते हुए, एक पूर्ण बहुपद <math>f</math> इस वर्ग के लिए दो गुणों वाला एक बहुपद है: (1) यह वर्ग का हिस्सा है, और (2) कोई अन्य बहुपद <math>g</math> की तुलना में कक्षा में आसान है <math>f,</math> इस अर्थ में कि यदि <math>f</math> एक छोटा सर्किट है तो ऐसा होता है <math>g.</math> वैलेंट ने दिखाया कि VNP वर्ग के लिए स्थायी पूर्ण है। तो यह दिखाने के लिए कि वीपी वीएनपी के बराबर नहीं है, किसी को यह दिखाने की जरूरत है कि स्थायी में बहुपद आकार के सर्किट नहीं होते हैं। यह एक उत्कृष्ट खुली समस्या बनी हुई है।
+जटिलता सिद्धांत में बुनियादी धारणाओं में से एक पूर्णता की धारणा है। बहुपदों के एक वर्ग (जैसे VP या VNP) को देखते हुए, एक पूर्ण बहुपद <math>f</math> इस वर्ग के लिए दो गुणों वाला एक बहुपद है: (1) यह वर्ग का हिस्सा है, और (2) कोई अन्य बहुपद <math>g</math> की तुलना में कक्षा <math>f,</math> में आसान है  इस अर्थ में कि यदि <math>f</math> एक छोटा परिपथ है तो ऐसा <math>g.</math>करता है। वैलेंट ने दिखाया कि VNP वर्ग के लिए स्थायी पूर्ण है। इसलिये यह दिखाने के लिए किVP, VNP के बराबर नहीं है, किसी को यह दिखाने की जरूरत है कि स्थायी में बहुपद आकार के परिपथ नहीं होते हैं। यह एक उत्कृष्ट खुली समस्या बनी हुई है।
 == गहराई में कमी ==
-बहुपदों की गणना की हमारी समझ में एक बेंचमार्क वैलिएंट, स्काईम, बर्कोविट्ज और रैकॉफ का काम है।<ref>L. G. Valiant, S. Skyum, S. Berkowitz, C. Rackoff. ''Fast parallel computation of polynomials using few processors.'' SIAM J. Comput. 12(4), pp. 641–644, 1983.</ref> उन्होंने दिखाया कि यदि एक बहुपद <math>f</math> डिग्री का <math>r</math> आकार का एक सर्किट है <math>s,</math> तब <math>f </math> में आकार बहुपद का एक सर्किट भी है <math>r</math> और <math>s</math> गहराई का <math>O(\log(r) \log(s)).</math> उदाहरण के लिए, डिग्री का कोई बहुपद <math>n</math> जिसमें बहुपद आकार का परिपथ होता है, मोटे तौर पर गहराई का बहुपद आकार परिपथ भी होता है <math>\log^2 (n).</math> यह परिणाम बर्कोविट्ज़ के सर्किट को बहुपद डिग्री के किसी भी बहुपद के लिए सामान्यीकृत करता है जिसमें बहुपद आकार सर्किट (जैसे निर्धारक) होता है। बूलियन सेटिंग में इस परिणाम का एनालॉग गलत माना जाता है।
+बहुपदों की गणना की हमारी समझ में एक मानदण्ड वैलिएंट, स्काईम, बर्कोविट्ज और रैकॉफ का काम है।<ref>L. G. Valiant, S. Skyum, S. Berkowitz, C. Rackoff. ''Fast parallel computation of polynomials using few processors.'' SIAM J. Comput. 12(4), pp. 641–644, 1983.</ref> उन्होंने दिखाया कि यदि एक बहुपद <math>f</math>  कोटि <math>r</math> का  आकार <math>s,</math> का एक परिपथ है  तब बहुपद <math>f </math> में  <math>r</math> और <math>s</math>आकार का <math>O(\log(r) \log(s)).</math> गहराई का  एक परिपथ भी है।उदाहरण के लिए,<math>n</math>  कोटि का कोई बहुपद जिसमें बहुपद आकार का परिपथ होता है, लगभग <math>\log^2 (n).</math>गहराई का बहुपद आकार परिपथ भी होता है  यह परिणाम बर्कोविट्ज़ के परिपथ को बहुपद  कोटि के किसी भी बहुपद के लिए सामान्यीकृत करता है जिसमें बहुपद आकार परिपथ(जैसे निर्धारक) होता है। बूलियन व्यवस्थान में इस परिणाम का एनालॉग गलत माना जाता है।
-इस परिणाम का एक परिणाम अपेक्षाकृत छोटे सूत्रों द्वारा परिपथों का अनुकरण है, अर्धबहुपद आकार के सूत्र: यदि एक बहुपद <math>f</math> डिग्री का <math>r</math> आकार का एक सर्किट है <math>s,</math> तो इसका आकार का एक सूत्र है <math>s^{O(\log(r))}.</math> यह अनुकरण Valiant el al की गहराई में कमी से आसान है। और पहले हयाफिल द्वारा दिखाया गया था।<ref>L. Hyafil. ''On the parallel evaluation of multivariate polynomials.'' SIAM J. Comput. 8(2), pp. 120–123, 1979.</ref>
+इस परिणाम का एक परिणाम अपेक्षाकृत छोटे सूत्रों द्वारा परिपथों का अनुकरण है, अर्धबहुपद आकार के सूत्र: यदि एक बहुपद <math>f</math>, <math>r</math> कोटि का <math>s,</math> आकार का एक परिपथ है तो इसके आकार का एक सूत्र है <math>s^{O(\log(r))}.</math> यह अनुकरण वैलियन्ट अल अल की गहराई में कमी से आसान है और पहले हयाफिल द्वारा दिखाया गया था।<ref>L. Hyafil. ''On the parallel evaluation of multivariate polynomials.'' SIAM J. Comput. 8(2), pp. 120–123, 1979.</ref>
@@ Line 56: / Line 56: @@
 श्रेणी:सर्किट जटिलता
+[[Category:Created On 12/05/2023|Arithmetic Circuit Complexity]]
-[[Category: Machine Translated Page]]
+[[Category:Machine Translated Page|Arithmetic Circuit Complexity]]
-[[Category:Created On 12/05/2023]]
+[[Category:Pages with script errors|Arithmetic Circuit Complexity]]
+[[Category:Templates Vigyan Ready|Arithmetic Circuit Complexity]]

Anonymous

Search

अंकगणितीय परिपथ सम्मिश्रता: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 09:24, 12 June 2023

Contents

परिभाषाएँ

अवलोकन

ऊपरी सीमा

निचली सीमाएं

बीजगणितीय पी और एनपी

गहराई में कमी

यह भी देखें

अग्रिम पठन

फुटनोट्स

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

अंकगणितीय परिपथ सम्मिश्रता: Difference between revisions

Latest revision as of 09:24, 12 June 2023

परिभाषाएँ

अवलोकन

ऊपरी सीमा

निचली सीमाएं

बीजगणितीय पी और एनपी

गहराई में कमी

यह भी देखें

अग्रिम पठन

फुटनोट्स

Navigation

Wiki tools

Page tools

Other projects

Hidden categories