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

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

परिभाषाएँ

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

एक अंकगणितीय सर्किट $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}$

(यह एक गहराई तीन सर्किट है)।

As part of the study of the complexity of computing polynomials, some clever circuits (alternatively algorithms) were found. A well-known example is Strassen's algorithm for matrix product. The straightforward way for computing the product of two  matrices requires a circuit of size order  Strassen showed that we can, in fact, multiply two matrices using a circuit of size roughly  Strassen's basic idea is a clever way for multiplying  matrices. This idea is the starting point of the best theoretical way for multiplying two matrices that takes time roughly

Another interesting story lies behind the computation of the determinant of an  matrix. The naive way for computing the determinant requires circuits of size roughly  Nevertheless, we know that there are circuits of size polynomial in  for computing the determinant. These circuits, however, have depth that is linear in  Berkowitz came up with an improvement: a circuit of size polynomial in  but of depth

We would also like to mention the best circuit known for the permanent of an  matrix. As for the determinant, the naive circuit for the permanent has size roughly  However, for the permanent the best circuit known has size roughly  which is given by Ryser's formula: for an  matrix

निचली सीमाएं

निचली सीमा सिद्ध करने के कारक में, हमारा ज्ञान बहुत सीमित है। चूंकि हम औपचारिक बहुपदों की गणना का अध्ययन करते हैं, हम जानते हैं कि बहुत बड़ी डिग्री के बहुपदों के लिए बड़े परिपथों की आवश्यकता होती है, उदाहरण के लिए, डिग्री का बहुपद $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),$ और बाद में बाउर और स्ट्रैसन ने निम्नलिखित दिखाया: आकार का एक अंकगणितीय सर्किट दिया $s$ एक बहुपद की गणना $f,$ कोई अधिक से अधिक आकार का एक नया परिपथ बना सकता है $O(s)$ जो गणना करता है $f$ और सभी $n$ का आंशिक व्युत्पन्न $f.$ के आंशिक डेरिवेटिव के बाद से $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 समस्या।

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

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

गहराई में कमी

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

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

यह भी देखें

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

अग्रिम पठन

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

फुटनोट्स

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