अंकगणितीय परिपथ सम्मिश्रता: Difference between revisions
No edit summary |
No edit summary |
||
| Line 2: | Line 2: | ||
== परिभाषाएँ == | == परिभाषाएँ == | ||
[[Image:ArithmeticCircuit.svg|right|frame|एक साधारण अंकगणितीय सर्किट।]]एक अंकगणितीय सर्किट <math>C</math> क्षेत्र के ऊपर (गणित) <math>F</math> और चर का सेट <math>x_1, \ldots, x_n</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>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>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>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> \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> | ||
(यह एक गहराई तीन सर्किट है)। | (यह एक गहराई तीन सर्किट है)। | ||
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 | |||
=== निचली सीमाएं === | === निचली सीमाएं === | ||
निचली सीमा सिद्ध करने के | निचली सीमा सिद्ध करने के कारक में, हमारा ज्ञान बहुत सीमित है। चूंकि हम औपचारिक बहुपदों की गणना का अध्ययन करते हैं, हम जानते हैं कि बहुत बड़ी डिग्री के बहुपदों के लिए बड़े परिपथों की आवश्यकता होती है, उदाहरण के लिए, डिग्री का बहुपद <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>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> भी। यह एक उदाहरण है जहां कुछ ऊपरी सीमा निचली सीमा को साबित करने में मदद करती है; बाउर और स्ट्रैसन द्वारा दिए गए सर्किट के निर्माण से अधिक सामान्य बहुपदों के लिए एक निचली सीमा का पता चलता है। | ||
निचली सीमाओं को साबित करने की क्षमता की कमी हमें संगणना के सरल मॉडल पर विचार करने के लिए प्रेरित करती है। कुछ उदाहरण हैं: मोनोटोन सर्किट (जिसमें सभी क्षेत्र तत्व गैर-ऋणात्मक वास्तविक संख्याएं हैं), निरंतर गहराई वाले सर्किट, और मल्टीलाइनियर सर्किट (जिसमें | निचली सीमाओं को साबित करने की क्षमता की कमी हमें संगणना के सरल मॉडल पर विचार करने के लिए प्रेरित करती है। कुछ उदाहरण हैं: मोनोटोन सर्किट (जिसमें सभी क्षेत्र तत्व गैर-ऋणात्मक वास्तविक संख्याएं हैं), निरंतर गहराई वाले सर्किट, और मल्टीलाइनियर सर्किट (जिसमें हरफाटकएक [[बहुरेखीय बहुपद]] की गणना करता है)। इन प्रतिबंधित मॉडलों का बड़े पैमाने पर अध्ययन किया गया है और कुछ समझ और परिणाम प्राप्त हुए हैं। | ||
== बीजीय पी और एनपी == | == बीजीय पी और एनपी == | ||
Revision as of 19:10, 26 May 2023
कम्प्यूटेशनल जटिलता सिद्धांत में, अंकगणितीय सर्किट बहुपदों की गणना के लिए मानक मॉडल हैं। अनौपचारिक रूप से, एक अंकगणितीय सर्किट इनपुट के रूप में या तो चर या संख्या लेता है, और इसे पहले से ही गणना की गई दो अभिव्यक्तियों को जोड़ने या गुणा करने की अनुमति है। अंकगणितीय सर्किट कंप्यूटिंग बहुपदों की जटिलता को समझने का एक औपचारिक तरीका प्रदान करते हैं। शोध की इस पंक्ति में मूल प्रकार का प्रश्न यह है कि किसी दिए गए बहुपद की गणना करने का सबसे कुशल तरीका क्या है?
परिभाषाएँ
एक अंकगणितीय सर्किट क्षेत्र के ऊपर (गणित) और चर का सेट इस प्रकार एक निर्देशित अचक्रिय ग्राफ है। इसमें प्रत्येक नोड को अंतःकोटि शून्य के साथ एक इनपुटफाटककहा जाता है और इसे एक चर या एक क्षेत्र तत्व में द्वारा लेबल किया जाता है। हर दूसरे फाटकको या द्वारा लेबल किया जाता है पहली स्थिति में यह योग द्वार है और दूसरी स्थिति में गुणन द्वार है। एक अंकगणितीय सूत्र एक सर्किट है जिसमें प्रत्येक द्वार एक से आगे निकल जाता है (और इसलिए अंतर्निहित ग्राफ एक निर्देशित पेड़ है)।
एक परिपथ के साथ जटिलता के दो माप जुड़े होते हैं: आकार और गहराई। एक सर्किट का आकार उसमें फाटकों की संख्या है, और एक सर्किट की गहराई उसमें सबसे लंबे निर्देशित पथ की लंबाई है। उदाहरण के लिए, आकृति में सर्किट का आकार छह और गहराई दो है।
एक अंकगणितीय सर्किट निम्नलिखित प्राकृतिक तरीके से एक बहुपद की गणना करता है। एक इनपुट फाटक उस बहुपद की गणना करता है जिसके द्वारा इसे लेबल किया जाता है। एक योग द्वार अपने बच्चों द्वारा गणना किए गए बहुपदों के योग की गणना करता है (एक फाटक का बच्चा है यदि निर्देशित किनारा ग्राफ में है)। एक गुणन फाटक अपने बच्चों द्वारा गणना की गई बहुपदों के गुणन की गणना करता है। चित्र में सर्किट पर विचार करें, उदाहरण के लिए: इनपुट फाटक गणना (बाएं से दाएं) और योग फाटक गणना और और गुणन फाटक गणना करता है।
अवलोकन
एक दिया गया बहुपद हम अपने आप से पूछ सकते हैं कि इसकी गणना करने का सबसे अच्छा तरीका क्या है - उदाहरण के लिए, सर्किट कंप्यूटिंग का सबसे छोटा आकार क्या है ,इस प्रश्न के उत्तर में दो भाग होते हैं। पहला भाग गणना करने वाले कुछ सर्किट ढूंढ रहा है इस हिस्से को सामान्यतः की ऊपरी सीमा की जटिलता कहा जाता है।दूसरा भाग दिखा रहा है कि कोई अन्य सर्किट अधिक अच्छा नहीं कर सकता; इस हिस्से को की 'निचली सीमा' जटिलता कहा जाता है।यद्यपि ये दो कार्य दृढ़ता से संबंधित हैं, निचली सीमा को साबित करना सामान्यतः कठिन होता है, क्योंकि निचली सीमा को साबित करने के लिए एक ही समय में सभी सर्किटों के बारे में बहस करने की आवश्यकता होती है।
ध्यान दें कि हम बहुपदों को परिभाषित करने वाले कार्यों के अतिरिक्त बहुपदों की औपचारिक गणना में रुचि रखते हैं। उदाहरण के लिए, बहुपद पर विचार करें,दो तत्वों के क्षेत्र में यह बहुपद शून्य कार्य का प्रतिनिधित्व करता है, लेकिन यह शून्य बहुपद नहीं है। यह अंकगणितीय परिपथों के अध्ययन और बूलियन परिपथों के अध्ययन के बीच के अंतरों में से एक है। बूलियन जटिलता में, किसी को इसके कुछ प्रतिनिधित्व (हमारे कारक में, एक बहुपद द्वारा प्रतिनिधित्व) के अतिरिक्त किसी फलन की गणना करने में अधिक रुचि होती है। यह उन कारणों में से एक है जो बूलियन जटिलता को अंकगणितीय जटिलता से कठिन बनाते हैं। अंकगणितीय परिपथों के अध्ययन को भी बूलियन कारक केअध्ययन की दिशा में मध्यवर्ती चरणों में से एक माना जा सकता है,[1] जिसे हम कम ही समझ पाते हैं।
ऊपरी सीमा
कंप्यूटिंग बहुपदों की जटिलता के अध्ययन के भाग के रूप में, कुछ चालाक सर्किट (वैकल्पिक रूप से एल्गोरिदम) पाए गए। एक प्रसिद्ध उदाहरण है वोल्कर स्ट्रैसेन | मैट्रिक्स गुणन के लिए स्ट्रैसेन का एल्गोरिदम। दो के गुणन की गणना करने का सीधा तरीका मेट्रिसेस को आकार क्रम के एक सर्किट की आवश्यकता होती है स्ट्रैसन ने दिखाया कि वास्तव में, हम मोटे तौर पर आकार के सर्किट का उपयोग करके दो आव्यूहों को गुणा कर सकते हैं स्ट्रैसन का मूल विचार गुणा करने का एक चतुर तरीका है मैट्रिक्स। यह विचार मैट्रिक्स गुणन की कम्प्यूटेशनल जटिलता का प्रारंभिक बिंदु है जिसमें मोटे तौर पर समय लगता है एक के निर्धारक की गणना के पीछे एक और दिलचस्प कहानी है आव्यूह। निर्धारक की गणना करने के सरल तरीके के लिए मोटे तौर पर आकार के सर्किट की आवश्यकता होती है फिर भी, हम जानते हैं कि आकार बहुपद के परिपथ होते हैं निर्धारक की गणना के लिए। हालाँकि, इन सर्किटों में गहराई होती है जो रैखिक होती है बर्कोविट्ज़ एक सुधार के साथ आया: आकार बहुपद का एक सर्किट लेकिन गहराई का [2] हम एक के स्थायी (गणित) के लिए ज्ञात सर्वोत्तम परिपथ का भी उल्लेख करना चाहेंगे आव्यूह। निर्धारक के रूप में, स्थायी के लिए भोली सर्किट का आकार लगभग होता है हालांकि, स्थायी रूप से ज्ञात सर्वश्रेष्ठ सर्किट का आकार मोटे तौर पर होता है जो रायसर के सूत्र द्वारा दिया गया है: एक के लिए आव्यूह
(यह एक गहराई तीन सर्किट है)।
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
निचली सीमाएं
निचली सीमा सिद्ध करने के कारक में, हमारा ज्ञान बहुत सीमित है। चूंकि हम औपचारिक बहुपदों की गणना का अध्ययन करते हैं, हम जानते हैं कि बहुत बड़ी डिग्री के बहुपदों के लिए बड़े परिपथों की आवश्यकता होती है, उदाहरण के लिए, डिग्री का बहुपद मोटे तौर पर आकार के एक सर्किट की आवश्यकता होती है तो, मुख्य लक्ष्य छोटी डिग्री के बहुपदों के लिए निचली बाध्यता साबित करना है, कहें, बहुपद में वास्तव में, जैसा कि गणित के कई क्षेत्रों में होता है, गिनती के तर्क हमें बताते हैं कि बहुपद डिग्री के बहुपद हैं जिनके लिए सुपरपोलिनोमियल आकार के सर्किट की आवश्यकता होती है। हालाँकि, ये गिनती के तर्क सामान्यतःगणना की हमारी समझ में सुधार नहीं करते हैं। अनुसंधान के इस क्षेत्र में निम्नलिखित समस्या मुख्य खुली समस्या है: बहुपद डिग्री का एक 'स्पष्ट' बहुपद खोजें जिसके लिए सुपरपोलिनोमियल आकार के सर्किट की आवश्यकता होती है।
कला की स्थिति एक है एक सर्किट कंप्यूटिंग के आकार के लिए निचली सीमा, उदाहरण के लिए, बहुपद वोल्कर स्ट्रास और बाउर और स्ट्रैसन द्वारा दिया गया। अधिक सटीक रूप से, स्ट्रैसन ने बेज़ाउट लेम्मा का उपयोग यह दिखाने के लिए किया कि कोई भी सर्किट जो एक साथ गणना करता है बहुआयामी पद आकार का है और बाद में बाउर और स्ट्रैसन ने निम्नलिखित दिखाया: आकार का एक अंकगणितीय सर्किट दिया एक बहुपद की गणना कोई अधिक से अधिक आकार का एक नया परिपथ बना सकता है जो गणना करता है और सभी का आंशिक व्युत्पन्न के आंशिक डेरिवेटिव के बाद से हैं स्ट्रैसन की निचली सीमा लागू होती है भी। यह एक उदाहरण है जहां कुछ ऊपरी सीमा निचली सीमा को साबित करने में मदद करती है; बाउर और स्ट्रैसन द्वारा दिए गए सर्किट के निर्माण से अधिक सामान्य बहुपदों के लिए एक निचली सीमा का पता चलता है।
निचली सीमाओं को साबित करने की क्षमता की कमी हमें संगणना के सरल मॉडल पर विचार करने के लिए प्रेरित करती है। कुछ उदाहरण हैं: मोनोटोन सर्किट (जिसमें सभी क्षेत्र तत्व गैर-ऋणात्मक वास्तविक संख्याएं हैं), निरंतर गहराई वाले सर्किट, और मल्टीलाइनियर सर्किट (जिसमें हरफाटकएक बहुरेखीय बहुपद की गणना करता है)। इन प्रतिबंधित मॉडलों का बड़े पैमाने पर अध्ययन किया गया है और कुछ समझ और परिणाम प्राप्त हुए हैं।
बीजीय पी और एनपी
कम्प्यूटेशनल जटिलता सिद्धांत में सबसे दिलचस्प खुली समस्या P बनाम NP समस्या है। मोटे तौर पर, यह समस्या यह निर्धारित करने के लिए है कि क्या दी गई समस्या को उतनी ही आसानी से हल किया जा सकता है, जितनी आसानी से यह दिखाया जा सकता है कि दी गई समस्या का समाधान मौजूद है। अपने सेमिनल वर्क वैलेंट में[3] इस समस्या के एक बीजीय अनुरूप का सुझाव दिया, VP बनाम VNP समस्या।
कक्षा वीपी पी का बीजगणितीय अनुरूप है; यह बहुपदों का वर्ग है बहुपद की डिग्री जिसमें एक निश्चित क्षेत्र पर बहुपद आकार के सर्किट होते हैं वीएनपी वर्ग एनपी का एनालॉग है। VNP को बहुपदों के वर्ग के रूप में माना जा सकता है बहुपद डिग्री की ऐसी है कि एक मोनोमियल दिए जाने पर हम इसके गुणांक को निर्धारित कर सकते हैं कुशलतापूर्वक, एक बहुपद आकार सर्किट के साथ।
जटिलता सिद्धांत में बुनियादी धारणाओं में से एक पूर्णता की धारणा है। बहुपदों के एक वर्ग (जैसे वीपी या वीएनपी) को देखते हुए, एक पूर्ण बहुपद इस वर्ग के लिए दो गुणों वाला एक बहुपद है: (1) यह वर्ग का हिस्सा है, और (2) कोई अन्य बहुपद की तुलना में कक्षा में आसान है इस अर्थ में कि यदि एक छोटा सर्किट है तो ऐसा होता है वैलेंट ने दिखाया कि VNP वर्ग के लिए स्थायी पूर्ण है। तो यह दिखाने के लिए कि वीपी वीएनपी के बराबर नहीं है, किसी को यह दिखाने की जरूरत है कि स्थायी में बहुपद आकार के सर्किट नहीं होते हैं। यह एक उत्कृष्ट खुली समस्या बनी हुई है।
गहराई में कमी
बहुपदों की गणना की हमारी समझ में एक बेंचमार्क वैलिएंट, स्काईम, बर्कोविट्ज और रैकॉफ का काम है।[4] उन्होंने दिखाया कि यदि एक बहुपद डिग्री का आकार का एक सर्किट है तब में आकार बहुपद का एक सर्किट भी है और गहराई का उदाहरण के लिए, डिग्री का कोई बहुपद जिसमें बहुपद आकार का परिपथ होता है, मोटे तौर पर गहराई का बहुपद आकार परिपथ भी होता है यह परिणाम बर्कोविट्ज़ के सर्किट को बहुपद डिग्री के किसी भी बहुपद के लिए सामान्यीकृत करता है जिसमें बहुपद आकार सर्किट (जैसे निर्धारक) होता है। बूलियन सेटिंग में इस परिणाम का एनालॉग गलत माना जाता है।
इस परिणाम का एक परिणाम अपेक्षाकृत छोटे सूत्रों द्वारा परिपथों का अनुकरण है, अर्धबहुपद आकार के सूत्र: यदि एक बहुपद डिग्री का आकार का एक सर्किट है तो इसका आकार का एक सूत्र है यह अनुकरण Valiant el al की गहराई में कमी से आसान है। और पहले हयाफिल द्वारा दिखाया गया था।[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.
श्रेणी:सर्किट जटिलता
