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

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

परिभाषाएँ

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

एक अंकगणितीय सर्किट $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),$ और बाद में बाउर और स्ट्रैसन ने निम्नलिखित दिखाया: आकार का एक अंकगणितीय सर्किट दिया $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.

फुटनोट्स

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