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

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

परिभाषाएँ

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

एक अंकगणितीय परिपथ $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;$ पर विचार करें,दो तत्वों के क्षेत्र में यह बहुपद शून्य कार्य का प्रतिनिधित्व करता है, लेकिन यह शून्य बहुपद नहीं है। यह अंकगणितीय परिपथों के अध्ययन और बूलियन परिपथों के अध्ययन के बीच के अंतरों में से एक है। बूलियन जटिलता में, किसी को इसके कुछ प्रतिनिधित्व (हमारे कारक में, एक बहुपद द्वारा प्रतिनिधित्व) के अतिरिक्त किसी फलन की गणना करने में अधिक रुचि होती है। यह उन कारणों में से एक है जो बूलियन जटिलता को अंकगणितीय जटिलता से कठिन बनाते हैं। अंकगणितीय परिपथों के अध्ययन को भी बूलियन कारक केअध्ययन की दिशा में मध्यवर्ती चरणों में से एक माना जा सकता है, जिसे हम कम ही समझ पाते हैं।

ऊपरी सीमा

कंप्यूटिंग बहुपदों की जटिलता के अध्ययन के भाग के रूप में, कुछ चालाक परिपथ (वैकल्पिक रूप से एल्गोरिदम) पाए गए। मैट्रिक्स गुणन के लिए स्ट्रैसेन का एल्गोरिदम एक प्रसिद्ध उदाहरण है। दो के$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)).$ गहराई का।

हम एक $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 समस्या है। लगभग, यह समस्या यह निर्धारित करने के लिए है कि क्या दी गई समस्या को उतनी ही आसानी से हल किया जा सकता है, जितनी आसानी से यह दिखाया जा सकता है कि दी गई समस्या का समाधान उपस्थित है। अपने बीजीय कार्य उपस्थिति में इस समस्या के एक बीजीय अनुरूप का सुझाव दिया, VP विरुद्ध VNP समस्या है।

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

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

गहराई में कमी

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

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

यह भी देखें

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

अग्रिम पठन

• 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.

फुटनोट्स

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