सर्किट जटिलता: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Model of computational complexity}} | {{Short description|Model of computational complexity}} | ||
[[सैद्धांतिक कंप्यूटर विज्ञान]] में, | [[सैद्धांतिक कंप्यूटर विज्ञान]] में, परिपथ जटिलता [[कम्प्यूटेशनल जटिलता सिद्धांत]] की शाखा है जिसमें बूलियन कार्यों को [[बूलियन सर्किट|बूलियन परिपथ]] के आकार या गहराई के अनुसार वर्गीकृत किया जाता है जो उनकी गणना करते हैं। संबंधित धारणा [[पुनरावर्ती भाषा]] की परिपथ जटिलता है जो मशीन है जो सदैव परिपथ के समान वर्ग द्वारा रुकती है <math>C_{1},C_{2},\ldots</math> (नीचे देखें)। | ||
स्पष्ट बूलियन कार्यों की गणना करने वाले बूलियन | स्पष्ट बूलियन कार्यों की गणना करने वाले बूलियन परिपथ के आकार पर निचली सीमा प्रदान करना जटिलता वर्गों को अलग करने का लोकप्रिय विधि है। उदाहरण के लिए, P/पॉली या इसका महत्व P/पॉली परिपथ क्लास P/पॉली में बहुपद आकार के परिपथ द्वारा गणना योग्य बूलियन फ़ंक्शन होते हैं। यह सिद्ध करना <math>\mathsf{NP}\not\subseteq \mathsf{P/poly}</math> [[पी (जटिलता)]] और [[एनपी (जटिलता)]] को अलग करेगा (नीचे देखें)। | ||
बूलियन सर्किट के संदर्भ में परिभाषित जटिलता वर्गों में एसी0, एसी, टीसी0, एनसी1, एनसी और पी/पॉली सम्मिलित हैं। | बूलियन सर्किट के संदर्भ में परिभाषित जटिलता वर्गों में एसी0, एसी, टीसी0, एनसी1, एनसी और पी/पॉली सम्मिलित हैं। | ||
== आकार और गहराई == | == आकार और गहराई == | ||
n इनपुट बिट्स के साथ बूलियन | n इनपुट बिट्स के साथ बूलियन परिपथ एक निर्देशित अचक्रीय ग्राफ है जिसमें प्रत्येक नोड (सामान्यतः इस संदर्भ में गेट्स कहा जाता है) या तो [[इन-डिग्री]] 0 का इनपुट नोड होता है जिसे किसी द्वारा लेबल किया जाता है। <math>n</math> इनपुट बिट्स, एंड गेट, औरगेट या नॉटगेट। इनमें से गेट को आउटपुट गेट के रूप में नामित किया गया है। ऐसा परिपथ स्वाभाविक रूप से इसके फ़ंक्शन की गणना करता है <math>n</math> आदानों। परिपथ का आकार इसमें सम्मिलित फाटकों की संख्या है और इसकी गहराई इनपुट गेट से आउटपुट गेट तक पथ की अधिकतम लंबाई है। | ||
परिपथ जटिलता की दो प्रमुख धारणाएँ हैं<ref name="Sipser_1997"/> <math>f</math> बूलियन फलन की | परिपथ जटिलता की दो प्रमुख धारणाएँ हैं<ref name="Sipser_1997"/> <math>f</math> बूलियन फलन की परिपथ-आकार की जटिलता <math>f</math> किसी भी परिपथ कंप्यूटिंग का न्यूनतम आकार है <math>f</math>. बूलियन फ़ंक्शन की परिपथ-गहराई जटिलता <math>f</math> किसी भी परिपथ कंप्यूटिंग की न्यूनतम गहराई है . | ||
ये धारणाएं सामान्यीकृत होती हैं जब कोई किसी भाषा की | ये धारणाएं सामान्यीकृत होती हैं जब कोई किसी भाषा की परिपथ जटिलता पर विचार करता है जिसमें अलग-अलग बिट लंबाई वाले तार होते हैं, विशेष रूप से अनंत [[औपचारिक भाषा]]एं। यद्यपि, बूलियन परिपथ केवल निश्चित संख्या में इनपुट बिट्स की अनुमति देते हैं। इस प्रकार, कोई एकल बूलियन परिपथ ऐसी भाषा तय करने में सक्षम नहीं है। इस संभावना को ध्यान में रखते हुए, परिपथ के वर्गों पर विचार किया जाता है <math>C_{1},C_{2},\ldots</math> जहां प्रत्येक <math>C_{n}</math> आकार के इनपुट स्वीकार करता है <math>n</math>. प्रत्येक परिपथ वर्ग परिपथ द्वारा स्वाभाविक रूप से भाषा उत्पन्न करेगा <math>C_{n}</math> आउटपुटिंग <math>1</math> जब लंबाई <math>n</math> स्ट्रिंग वर्ग का सदस्य है, और <math>0</math> अन्यथा। हम कहते हैं कि परिपथ का वर्ग न्यूनतम आकार का होता है यदि कोई अन्य वर्ग नहीं है जो किसी भी आकार के इनपुट पर निर्णय लेता है, <math>n</math>, से छोटे आकार के परिपथ के साथ <math>C_n</math> (क्रमशः गहराई न्यूनतम वर्गों के लिए)। इस प्रकार, पुनरावर्ती भाषा | गैर-पुनरावर्ती भाषाओं के लिए भी परिपथ जटिलता सार्थक है। समान वर्ग की धारणा परिपथ जटिलता के वेरिएंट को पुनरावर्ती भाषाओं के एल्गोरिथ्म आधारित जटिलता उपायों से संबंधित होने में सक्षम बनाती है। चूंकि, दी गई भाषाओं को तय करने के लिए किसी भी परिपथ वर्ग को कितना जटिल होना चाहिए, इस पर निचली सीमाएं खोजने में गैर-समान संस्करण सहायक होता है। | ||
इसलिए, औपचारिक भाषा की | इसलिए, औपचारिक भाषा की परिपथ-आकार की जटिलता <math>A</math> समारोह के रूप में परिभाषित किया गया है <math>t:\mathbb{N}\to\mathbb{N}</math>, जो इनपुट की थोड़ी लंबाई से संबंधित है, <math>n</math>, न्यूनतम परिपथ के परिपथ-आकार की जटिलता के लिए <math>C_{n}</math> यह तय करता है कि उस लंबाई के इनपुट अंदर हैं या नहीं <math>A</math>. परिपथ-डेप्थ जटिलता को इसी तरह परिभाषित किया गया है। | ||
== एकरूपता == | == एकरूपता == | ||
बूलियन | बूलियन परिपथ तथाकथित गैर-समान सार मशीन के प्रमुख उदाहरणों में से हैं, इस अर्थ में कि अलग-अलग लंबाई के इनपुट को अलग-अलग परिपथ द्वारा संसाधित किया जाता है, इसके विपरीत [[ट्यूरिंग मशीन]] जैसे समान मॉडल के विपरीत, जहां सभी संभव के लिए ही कम्प्यूटेशनल डिवाइस का उपयोग किया जाता है। इनपुट लंबाई। व्यक्तिगत [[कम्प्यूटेशनल समस्या]] इस प्रकार बूलियन परिपथ के विशेष वर्ग से जुड़ी हुई है <math>C_1, C_2, \dots </math> जहां प्रत्येक <math>C_n</math> n बिट्स का परिपथ हैंडलिंग इनपुट है। इन वर्गों पर अधिकांशतः एकरूपता की शर्त लगाई जाती है, जिसके लिए कुछ संभावित [[कम्प्यूटेशनल संसाधन]] | संसाधन-बद्ध ट्यूरिंग मशीन के अस्तित्व की आवश्यकता होती है, जो इनपुट एन पर, व्यक्तिगत परिपथ का विवरण तैयार करती है। <math>C_n</math>. जब इस ट्यूरिंग मशीन का रनिंग टाइम बहुपद n में होता है, तो परिपथ वर्ग को P-वर्दी कहा जाता है। [[DLOGTIME]]- एकरूपता की कठोर आवश्यकता एसी जैसे उथले-गहराई वाले परिपथ-वर्गों के अध्ययन में विशेष रुचि रखती है<sup>0</sup> या टीसी<sup>0</उप>जब कोई संसाधन सीमा निर्दिष्ट नहीं की जाती है, तो एक भाषा पुनरावर्ती होती है (यानी, ट्यूरिंग मशीन द्वारा तय की जा सकती है) अगर और केवल अगर भाषा बूलियन सर्किट के एक समान वर्ग द्वारा तय की जाती है। | ||
=== बहुपद-समय की वर्दी === | === बहुपद-समय की वर्दी === | ||
बूलियन | बूलियन परिपथ का वर्ग <math>\{C_n:n \in \mathbb{N}\}</math> यदि [[नियतात्मक ट्यूरिंग मशीन]] M उपस्थ है, तो बहुपद-समय एकसमान है, जैसे कि | ||
* एम बहुपद समय में चलता है | * एम बहुपद समय में चलता है | ||
* सभी के लिए <math>n \in \mathbb{N}</math>, M का विवरण आउटपुट करता है <math>C_n</math> इनपुट पर <math>1^n</math> | * सभी के लिए <math>n \in \mathbb{N}</math>, M का विवरण आउटपुट करता है <math>C_n</math> इनपुट पर <math>1^n</math> | ||
| Line 26: | Line 26: | ||
=== लॉगस्पेस वर्दी === | === लॉगस्पेस वर्दी === | ||
बूलियन | बूलियन परिपथ का वर्ग <math>\{C_n:n \in \mathbb{N}\}</math> यदि नियतात्मक ट्यूरिंग मशीन M उपस्थ है, तो लॉगस्पेस एकसमान है, जैसे कि | ||
* एम लॉगरिदमिक स्पेस में चलता है | * एम लॉगरिदमिक स्पेस में चलता है | ||
* सभी के लिए <math>n \in \mathbb{N}</math>, M का विवरण आउटपुट करता है <math>C_n</math> इनपुट पर <math>1^n</math> | * सभी के लिए <math>n \in \mathbb{N}</math>, M का विवरण आउटपुट करता है <math>C_n</math> इनपुट पर <math>1^n</math> | ||
| Line 32: | Line 32: | ||
== इतिहास == | == इतिहास == | ||
1949 में | 1949 में परिपथ जटिलता [[क्लाउड शैनन]] के पास वापस जाती है,<ref name="Shannon_1949"/>जिन्होंने सिद्ध किया कि n चरों पर लगभग सभी बूलियन कार्यों के लिए आकार Θ(2) के परिपथों की आवश्यकता होती है<sup>एन</sup>/n). इस तथ्य के अतिरिक्त, जटिलता सिद्धांतवादी अब तक किसी भी स्पष्ट कार्य के लिए सुपरलीनियर लोअर बाउंड सिद्ध करने में असमर्थ रहे हैं। | ||
उपयोग किए गए | उपयोग किए गए परिपथ के वर्ग पर कुछ प्रतिबंधों के अनुसार अधिबहुपद निचली सीमाएं सिद्ध हुई हैं। पहला कार्य जिसके लिए अधिबहुपद परिपथ निचली सीमाएँ दिखाई गई थीं, समता फ़ंक्शन था, जो इसके इनपुट बिट्स मॉड्यूलो 2 के योग की गणना करता है। तथ्य यह है कि समानता AC0|AC में समाहित नहीं है।<sup>0</sup> पहली बार 1983 में अजताई द्वारा स्वतंत्र रूप से स्थापित किया गया था<ref name="Ajtai_1983"/><ref name="Ajtai-Komlós-Szemerédi_1983"/>और 1984 में फुर्स्ट, सक्से और सिप्सर द्वारा।<ref name="Furst-Saxe-Sipser_1984"/> बाद में 1987 में जोहान हास्ताद|हस्ताद द्वारा सुधार किया गया<ref name="Håstad_1987"/> स्थापित किया गया है कि समता फ़ंक्शन की गणना करने वाले निरंतर-गहराई वाले परिपथ के किसी भी वर्ग को घातीय आकार की आवश्यकता होती है। रज़बोरोव के परिणाम का विस्तार,<ref name="Razborov_1985"/>1987 में स्मोलेंस्की<ref name="Smolensky_1987"/> सिद्ध हुआ कि यह सच है तथापि परिपथ गेट्स के साथ संवर्धित हो, इसके इनपुट बिट्स मॉडुलो कुछ विषम प्राइम पी के योग की गणना करता है। | ||
क्लिक समस्या | के-क्लिक समस्या यह तय करने के लिए है कि क्या n शिखर पर दिए गए ग्राफ में आकार के आकार का चक्कर है। स्थिरांक n और k के किसी विशेष विकल्प के लिए, ग्राफ़ को बाइनरी में एन्कोड किया जा सकता है <math>{n \choose 2}</math> बिट्स, जो प्रत्येक संभावित किनारे के लिए इंगित करता है कि यह उपस्थ है या नहीं। फिर के-क्लिक समस्या को समारोह के रूप में औपचारिक रूप दिया जाता है <math>f_k:\{0,1\}^{{n \choose 2}}\to\{0,1\}</math> ऐसा है कि <math>f_k</math> आउटपुट 1 यदि और केवल तभी जब स्ट्रिंग द्वारा एन्कोड किए गए ग्राफ़ में आकार k का समूह होता है। कार्यों का यह | क्लिक समस्या | के-क्लिक समस्या यह तय करने के लिए है कि क्या n शिखर पर दिए गए ग्राफ में आकार के आकार का चक्कर है। स्थिरांक n और k के किसी विशेष विकल्प के लिए, ग्राफ़ को बाइनरी में एन्कोड किया जा सकता है <math>{n \choose 2}</math> बिट्स, जो प्रत्येक संभावित किनारे के लिए इंगित करता है कि यह उपस्थ है या नहीं। फिर के-क्लिक समस्या को समारोह के रूप में औपचारिक रूप दिया जाता है <math>f_k:\{0,1\}^{{n \choose 2}}\to\{0,1\}</math> ऐसा है कि <math>f_k</math> आउटपुट 1 यदि और केवल तभी जब स्ट्रिंग द्वारा एन्कोड किए गए ग्राफ़ में आकार k का समूह होता है। कार्यों का यह वर्ग मोनोटोन है और इसकी गणना परिपथ के वर्ग द्वारा की जा सकती है, किन्तु यह दिखाया गया है कि इसकी गणना मोनोटोन परिपथ के बहुपद-आकार के वर्ग द्वारा नहीं की जा सकती है (अर्थात, एंड और और गेट वाले परिपथ किन्तु बिना निषेध के)। 1985 में [[अलेक्जेंडर रज़बोरोव]] का मूल परिणाम<ref name="Razborov_1985"/> बाद में 1987 में अलोन और बोपना द्वारा घातीय-आकार के निचले हिस्से में सुधार किया गया।<ref name="Alon-Boppana_1987"/> 2008 में, रॉसमैन<ref name="Rossman_2008"/> ने दिखाया कि एंड, औरऔर नॉटगेट्स वाले स्थिर-गहराई वाले परिपथों के लिए आकार की आवश्यकता होती है <math>\Omega(n^{k/4})</math> औसत स्थितियोंे की जटिलता में भी के-क्लिक समस्या को हल करने के लिए। इसके अतिरिक्त, आकार का परिपथ है <math>n^{k/4+O(1)}</math> जो गणना करता है <math>f_k</math>. | ||
1999 में, [[घाव एक बार|घाव बार]] और [[पियरे मैकेंजी]] ने बाद में दिखाया कि मोनोटोन एनसी पदानुक्रम अनंत है।<ref name="Raz-McKenzie_1999"/> | 1999 में, [[घाव एक बार|घाव बार]] और [[पियरे मैकेंजी]] ने बाद में दिखाया कि मोनोटोन एनसी पदानुक्रम अनंत है।<ref name="Raz-McKenzie_1999"/> | ||
| Line 47: | Line 47: | ||
* समता असमान AC0|AC में नहीं है<sup>0</sup>, अजताई द्वारा 1983 में सिद्ध किया गया<ref name="Ajtai_1983"/><ref name="Ajtai-Komlós-Szemerédi_1983"/> साथ ही 1984 में फुर्स्ट, सक्से और सिप्सर द्वारा।<ref name="Furst-Saxe-Sipser_1984"/>* यूनिफ़ॉर्म TC0|TC<sup>0</sup> [[पीपी (जटिलता)]] में सख्ती से समाहित है, जिसे एलेंडर ने सिद्ध किया है।<ref name="Allender_1997"/> वर्ग S2P (जटिलता)|S{{su|p=P|b=2}}, पीपी<ref group="nb" name="NB1"/> और [[एमए (जटिलता)]]/1<ref name="Santhanam_2007"/> ( सलाह के साथ एमए) आकार में नहीं हैं ('' एन<sup>k</sup>) किसी भी स्थिर k के लिए। | * समता असमान AC0|AC में नहीं है<sup>0</sup>, अजताई द्वारा 1983 में सिद्ध किया गया<ref name="Ajtai_1983"/><ref name="Ajtai-Komlós-Szemerédi_1983"/> साथ ही 1984 में फुर्स्ट, सक्से और सिप्सर द्वारा।<ref name="Furst-Saxe-Sipser_1984"/>* यूनिफ़ॉर्म TC0|TC<sup>0</sup> [[पीपी (जटिलता)]] में सख्ती से समाहित है, जिसे एलेंडर ने सिद्ध किया है।<ref name="Allender_1997"/> वर्ग S2P (जटिलता)|S{{su|p=P|b=2}}, पीपी<ref group="nb" name="NB1"/> और [[एमए (जटिलता)]]/1<ref name="Santhanam_2007"/> ( सलाह के साथ एमए) आकार में नहीं हैं ('' एन<sup>k</sup>) किसी भी स्थिर k के लिए। | ||
* जबकि यह संदेह है कि गैर-वर्दी वर्ग ACC0 में बहुमत का कार्य सम्मिलित नहीं है, यह केवल 2010 में [[रयान विलियम्स (कंप्यूटर वैज्ञानिक)]] ने सिद्ध किया था {{nowrap|<math>\mathsf{NEXP} \not \subseteq \mathsf{ACC}^0</math>.<ref name="Williams_2011"/>}} | * जबकि यह संदेह है कि गैर-वर्दी वर्ग ACC0 में बहुमत का कार्य सम्मिलित नहीं है, यह केवल 2010 में [[रयान विलियम्स (कंप्यूटर वैज्ञानिक)]] ने सिद्ध किया था {{nowrap|<math>\mathsf{NEXP} \not \subseteq \mathsf{ACC}^0</math>.<ref name="Williams_2011"/>}} | ||
यह खुला है कि क्या नेक्स्पटाइम | यह खुला है कि क्या नेक्स्पटाइम के पास असमान टीसी है<sup>0</sup> परिपथ। | ||
परिपथ लोअर बाउंड्स के सबूत [[derandomization|डेरनडोमाईजेशन]] | परिपथ लोअर बाउंड्स के सबूत [[derandomization|डेरनडोमाईजेशन]] से दृढ़ता से जुड़े हुए हैं। सबूत है कि <math>\mathsf{P} = \mathsf{BPP}</math> इसका मतलब यह होगा कि या तो <math>\mathsf{NEXP} \not \subseteq \mathsf{P/poly}</math> या उस स्थायी की गणना बहुपद आकार और बहुपद डिग्री के गैर-समान अंकगणितीय परिपथ (बहुपद) द्वारा नहीं की जा सकती।<ref name="Kabanets-Impagliazzo_2004"/> | ||
1997 में, रज़बोरोव और रुडिच ने दिखाया कि स्पष्ट बूलियन कार्यों के लिए कई ज्ञात परिपथ निचली सीमाएं संबंधित परिपथ वर्ग के विरुद्ध तथाकथित [[प्राकृतिक प्रमाण]] के अस्तित्व का संकेत देती हैं।<ref name="Razborov-Rudich_1997"/> दूसरी ओर, पी/पॉली के खिलाफ उपयोगी प्राकृतिक गुण शक्तिशाली छद्म यादृच्छिक जनरेटर को तोड़ देंगे। इसे अधिकांशतः शक्तिशाली | 1997 में, रज़बोरोव और रुडिच ने दिखाया कि स्पष्ट बूलियन कार्यों के लिए कई ज्ञात परिपथ निचली सीमाएं संबंधित परिपथ वर्ग के विरुद्ध तथाकथित [[प्राकृतिक प्रमाण]] के अस्तित्व का संकेत देती हैं।<ref name="Razborov-Rudich_1997"/> दूसरी ओर, पी/पॉली के खिलाफ उपयोगी प्राकृतिक गुण शक्तिशाली छद्म यादृच्छिक जनरेटर को तोड़ देंगे। इसे अधिकांशतः शक्तिशाली परिपथ निचली सीमा सिद्ध करने के लिए प्राकृतिक सबूत बाधा के रूप में व्याख्या की जाती है। 2016 में, कारमोसिनो, इम्पैग्लियाज़ो, कबनेट्स और कोलोकोलोवा ने सिद्ध कर दिया कि कुशल शिक्षण एल्गोरिदम के निर्माण के लिए प्राकृतिक गुणों का भी उपयोग किया जा सकता है।<ref name="Carmosino-Impagliazzo-Kabanets-Kolokolova_2016"/> | ||
== जटिलता वर्ग == | == जटिलता वर्ग == | ||
कई | कई परिपथ जटिलता वर्गों को वर्ग पदानुक्रमों के संदर्भ में परिभाषित किया गया है। प्रत्येक गैर-ऋणात्मक पूर्णांक i के लिए, वर्ग NC (जटिलता)|NC होता है<sup>i</sup>, जिसमें गहराई के बहुपद-आकार के परिपथ सम्मिलित हैं <math>O(\log^i(n))</math>, बाउंडेड फैन-इन एंड, और, और नॉट गेट्स का उपयोग करना। इन सभी वर्गों की संघ एनसी चर्चा का विषय है। असीमित फैन-इन गेट्स पर विचार करके, कक्षाएं एसी (जटिलता) | एसी<sup>i</sup> और AC (जो NC के बराबर है) की रचना की जा सकती है। गेट्स के विभिन्न समुच्चयों की अनुमति देकर ही आकार और गहराई प्रतिबंधों के साथ कई अन्य परिपथ जटिलता वर्गों का निर्माण किया जा सकता है। | ||
== समय जटिलता से संबंध == | == समय जटिलता से संबंध == | ||
यदि कोई निश्चित भाषा, <math>A</math>, कॉम्प्लेक्सिटी क्लास | टाइम-कॉम्प्लेक्सिटी क्लास से संबंधित है <math>\text{TIME}(t(n))</math> किसी समारोह के लिए <math>t:\mathbb{N}\to\mathbb{N}</math>, तब <math>A</math> | यदि कोई निश्चित भाषा, <math>A</math>, कॉम्प्लेक्सिटी क्लास | टाइम-कॉम्प्लेक्सिटी क्लास से संबंधित है <math>\text{TIME}(t(n))</math> किसी समारोह के लिए <math>t:\mathbb{N}\to\mathbb{N}</math>, तब <math>A</math> परिपथ जटिलता है <math>\mathcal{O}(t(n) \log t(n))</math>. यदि भाषा को स्वीकार करने वाली ट्यूरिंग मशीन [[ट्यूरिंग मशीन समकक्ष]] है (जिसका अर्थ है कि यह इनपुट की परवाह किए बिना समान मेमोरी सेल को पढ़ती और लिखती है), तो <math>A</math> परिपथ जटिलता है <math>\mathcal{O}(t(n))</math>.<ref>{{Citation|first=Nicholas|last=Pippenger|authorlink=Nick Pippenger|first2=Michael J.|last2=Fischer|authorlink2=Michael J. Fischer|title=Relations Among Complexity Measures|journal=[[Journal of the ACM]]|year=1979|volume=26|issue=3|pages=361–381|doi=10.1145/322123.322138}} | ||
</ref> | </ref> | ||
Revision as of 11:44, 24 February 2023
सैद्धांतिक कंप्यूटर विज्ञान में, परिपथ जटिलता कम्प्यूटेशनल जटिलता सिद्धांत की शाखा है जिसमें बूलियन कार्यों को बूलियन परिपथ के आकार या गहराई के अनुसार वर्गीकृत किया जाता है जो उनकी गणना करते हैं। संबंधित धारणा पुनरावर्ती भाषा की परिपथ जटिलता है जो मशीन है जो सदैव परिपथ के समान वर्ग द्वारा रुकती है (नीचे देखें)।
स्पष्ट बूलियन कार्यों की गणना करने वाले बूलियन परिपथ के आकार पर निचली सीमा प्रदान करना जटिलता वर्गों को अलग करने का लोकप्रिय विधि है। उदाहरण के लिए, P/पॉली या इसका महत्व P/पॉली परिपथ क्लास P/पॉली में बहुपद आकार के परिपथ द्वारा गणना योग्य बूलियन फ़ंक्शन होते हैं। यह सिद्ध करना पी (जटिलता) और एनपी (जटिलता) को अलग करेगा (नीचे देखें)।
बूलियन सर्किट के संदर्भ में परिभाषित जटिलता वर्गों में एसी0, एसी, टीसी0, एनसी1, एनसी और पी/पॉली सम्मिलित हैं।
आकार और गहराई
n इनपुट बिट्स के साथ बूलियन परिपथ एक निर्देशित अचक्रीय ग्राफ है जिसमें प्रत्येक नोड (सामान्यतः इस संदर्भ में गेट्स कहा जाता है) या तो इन-डिग्री 0 का इनपुट नोड होता है जिसे किसी द्वारा लेबल किया जाता है। इनपुट बिट्स, एंड गेट, औरगेट या नॉटगेट। इनमें से गेट को आउटपुट गेट के रूप में नामित किया गया है। ऐसा परिपथ स्वाभाविक रूप से इसके फ़ंक्शन की गणना करता है आदानों। परिपथ का आकार इसमें सम्मिलित फाटकों की संख्या है और इसकी गहराई इनपुट गेट से आउटपुट गेट तक पथ की अधिकतम लंबाई है।
परिपथ जटिलता की दो प्रमुख धारणाएँ हैं[1] बूलियन फलन की परिपथ-आकार की जटिलता किसी भी परिपथ कंप्यूटिंग का न्यूनतम आकार है . बूलियन फ़ंक्शन की परिपथ-गहराई जटिलता किसी भी परिपथ कंप्यूटिंग की न्यूनतम गहराई है .
ये धारणाएं सामान्यीकृत होती हैं जब कोई किसी भाषा की परिपथ जटिलता पर विचार करता है जिसमें अलग-अलग बिट लंबाई वाले तार होते हैं, विशेष रूप से अनंत औपचारिक भाषाएं। यद्यपि, बूलियन परिपथ केवल निश्चित संख्या में इनपुट बिट्स की अनुमति देते हैं। इस प्रकार, कोई एकल बूलियन परिपथ ऐसी भाषा तय करने में सक्षम नहीं है। इस संभावना को ध्यान में रखते हुए, परिपथ के वर्गों पर विचार किया जाता है जहां प्रत्येक आकार के इनपुट स्वीकार करता है . प्रत्येक परिपथ वर्ग परिपथ द्वारा स्वाभाविक रूप से भाषा उत्पन्न करेगा आउटपुटिंग जब लंबाई स्ट्रिंग वर्ग का सदस्य है, और अन्यथा। हम कहते हैं कि परिपथ का वर्ग न्यूनतम आकार का होता है यदि कोई अन्य वर्ग नहीं है जो किसी भी आकार के इनपुट पर निर्णय लेता है, , से छोटे आकार के परिपथ के साथ (क्रमशः गहराई न्यूनतम वर्गों के लिए)। इस प्रकार, पुनरावर्ती भाषा | गैर-पुनरावर्ती भाषाओं के लिए भी परिपथ जटिलता सार्थक है। समान वर्ग की धारणा परिपथ जटिलता के वेरिएंट को पुनरावर्ती भाषाओं के एल्गोरिथ्म आधारित जटिलता उपायों से संबंधित होने में सक्षम बनाती है। चूंकि, दी गई भाषाओं को तय करने के लिए किसी भी परिपथ वर्ग को कितना जटिल होना चाहिए, इस पर निचली सीमाएं खोजने में गैर-समान संस्करण सहायक होता है।
इसलिए, औपचारिक भाषा की परिपथ-आकार की जटिलता समारोह के रूप में परिभाषित किया गया है , जो इनपुट की थोड़ी लंबाई से संबंधित है, , न्यूनतम परिपथ के परिपथ-आकार की जटिलता के लिए यह तय करता है कि उस लंबाई के इनपुट अंदर हैं या नहीं . परिपथ-डेप्थ जटिलता को इसी तरह परिभाषित किया गया है।
एकरूपता
बूलियन परिपथ तथाकथित गैर-समान सार मशीन के प्रमुख उदाहरणों में से हैं, इस अर्थ में कि अलग-अलग लंबाई के इनपुट को अलग-अलग परिपथ द्वारा संसाधित किया जाता है, इसके विपरीत ट्यूरिंग मशीन जैसे समान मॉडल के विपरीत, जहां सभी संभव के लिए ही कम्प्यूटेशनल डिवाइस का उपयोग किया जाता है। इनपुट लंबाई। व्यक्तिगत कम्प्यूटेशनल समस्या इस प्रकार बूलियन परिपथ के विशेष वर्ग से जुड़ी हुई है जहां प्रत्येक n बिट्स का परिपथ हैंडलिंग इनपुट है। इन वर्गों पर अधिकांशतः एकरूपता की शर्त लगाई जाती है, जिसके लिए कुछ संभावित कम्प्यूटेशनल संसाधन | संसाधन-बद्ध ट्यूरिंग मशीन के अस्तित्व की आवश्यकता होती है, जो इनपुट एन पर, व्यक्तिगत परिपथ का विवरण तैयार करती है। . जब इस ट्यूरिंग मशीन का रनिंग टाइम बहुपद n में होता है, तो परिपथ वर्ग को P-वर्दी कहा जाता है। DLOGTIME- एकरूपता की कठोर आवश्यकता एसी जैसे उथले-गहराई वाले परिपथ-वर्गों के अध्ययन में विशेष रुचि रखती है0 या टीसी0</उप>जब कोई संसाधन सीमा निर्दिष्ट नहीं की जाती है, तो एक भाषा पुनरावर्ती होती है (यानी, ट्यूरिंग मशीन द्वारा तय की जा सकती है) अगर और केवल अगर भाषा बूलियन सर्किट के एक समान वर्ग द्वारा तय की जाती है।
बहुपद-समय की वर्दी
बूलियन परिपथ का वर्ग यदि नियतात्मक ट्यूरिंग मशीन M उपस्थ है, तो बहुपद-समय एकसमान है, जैसे कि
- एम बहुपद समय में चलता है
- सभी के लिए , M का विवरण आउटपुट करता है इनपुट पर
लॉगस्पेस वर्दी
बूलियन परिपथ का वर्ग यदि नियतात्मक ट्यूरिंग मशीन M उपस्थ है, तो लॉगस्पेस एकसमान है, जैसे कि
- एम लॉगरिदमिक स्पेस में चलता है
- सभी के लिए , M का विवरण आउटपुट करता है इनपुट पर
इतिहास
1949 में परिपथ जटिलता क्लाउड शैनन के पास वापस जाती है,[2]जिन्होंने सिद्ध किया कि n चरों पर लगभग सभी बूलियन कार्यों के लिए आकार Θ(2) के परिपथों की आवश्यकता होती हैएन/n). इस तथ्य के अतिरिक्त, जटिलता सिद्धांतवादी अब तक किसी भी स्पष्ट कार्य के लिए सुपरलीनियर लोअर बाउंड सिद्ध करने में असमर्थ रहे हैं।
उपयोग किए गए परिपथ के वर्ग पर कुछ प्रतिबंधों के अनुसार अधिबहुपद निचली सीमाएं सिद्ध हुई हैं। पहला कार्य जिसके लिए अधिबहुपद परिपथ निचली सीमाएँ दिखाई गई थीं, समता फ़ंक्शन था, जो इसके इनपुट बिट्स मॉड्यूलो 2 के योग की गणना करता है। तथ्य यह है कि समानता AC0|AC में समाहित नहीं है।0 पहली बार 1983 में अजताई द्वारा स्वतंत्र रूप से स्थापित किया गया था[3][4]और 1984 में फुर्स्ट, सक्से और सिप्सर द्वारा।[5] बाद में 1987 में जोहान हास्ताद|हस्ताद द्वारा सुधार किया गया[6] स्थापित किया गया है कि समता फ़ंक्शन की गणना करने वाले निरंतर-गहराई वाले परिपथ के किसी भी वर्ग को घातीय आकार की आवश्यकता होती है। रज़बोरोव के परिणाम का विस्तार,[7]1987 में स्मोलेंस्की[8] सिद्ध हुआ कि यह सच है तथापि परिपथ गेट्स के साथ संवर्धित हो, इसके इनपुट बिट्स मॉडुलो कुछ विषम प्राइम पी के योग की गणना करता है।
क्लिक समस्या | के-क्लिक समस्या यह तय करने के लिए है कि क्या n शिखर पर दिए गए ग्राफ में आकार के आकार का चक्कर है। स्थिरांक n और k के किसी विशेष विकल्प के लिए, ग्राफ़ को बाइनरी में एन्कोड किया जा सकता है बिट्स, जो प्रत्येक संभावित किनारे के लिए इंगित करता है कि यह उपस्थ है या नहीं। फिर के-क्लिक समस्या को समारोह के रूप में औपचारिक रूप दिया जाता है ऐसा है कि आउटपुट 1 यदि और केवल तभी जब स्ट्रिंग द्वारा एन्कोड किए गए ग्राफ़ में आकार k का समूह होता है। कार्यों का यह वर्ग मोनोटोन है और इसकी गणना परिपथ के वर्ग द्वारा की जा सकती है, किन्तु यह दिखाया गया है कि इसकी गणना मोनोटोन परिपथ के बहुपद-आकार के वर्ग द्वारा नहीं की जा सकती है (अर्थात, एंड और और गेट वाले परिपथ किन्तु बिना निषेध के)। 1985 में अलेक्जेंडर रज़बोरोव का मूल परिणाम[7] बाद में 1987 में अलोन और बोपना द्वारा घातीय-आकार के निचले हिस्से में सुधार किया गया।[9] 2008 में, रॉसमैन[10] ने दिखाया कि एंड, औरऔर नॉटगेट्स वाले स्थिर-गहराई वाले परिपथों के लिए आकार की आवश्यकता होती है औसत स्थितियोंे की जटिलता में भी के-क्लिक समस्या को हल करने के लिए। इसके अतिरिक्त, आकार का परिपथ है जो गणना करता है .
1999 में, घाव बार और पियरे मैकेंजी ने बाद में दिखाया कि मोनोटोन एनसी पदानुक्रम अनंत है।[11]
पूर्णांक विभाजन समस्या एकसमान TC0|TC में निहित है0।[12]
परिपथ निचली सीमा
परिपथ निचली सीमाएं सामान्यतः कठिन होती हैं। ज्ञात परिणाम सम्मिलित हैं
- समता असमान AC0|AC में नहीं है0, अजताई द्वारा 1983 में सिद्ध किया गया[3][4] साथ ही 1984 में फुर्स्ट, सक्से और सिप्सर द्वारा।[5]* यूनिफ़ॉर्म TC0|TC0 पीपी (जटिलता) में सख्ती से समाहित है, जिसे एलेंडर ने सिद्ध किया है।[13] वर्ग S2P (जटिलता)|SP
2, पीपी[nb 1] और एमए (जटिलता)/1[14] ( सलाह के साथ एमए) आकार में नहीं हैं ( एनk) किसी भी स्थिर k के लिए। - जबकि यह संदेह है कि गैर-वर्दी वर्ग ACC0 में बहुमत का कार्य सम्मिलित नहीं है, यह केवल 2010 में रयान विलियम्स (कंप्यूटर वैज्ञानिक) ने सिद्ध किया था .[15]
यह खुला है कि क्या नेक्स्पटाइम के पास असमान टीसी है0 परिपथ।
परिपथ लोअर बाउंड्स के सबूत डेरनडोमाईजेशन से दृढ़ता से जुड़े हुए हैं। सबूत है कि इसका मतलब यह होगा कि या तो या उस स्थायी की गणना बहुपद आकार और बहुपद डिग्री के गैर-समान अंकगणितीय परिपथ (बहुपद) द्वारा नहीं की जा सकती।[16]
1997 में, रज़बोरोव और रुडिच ने दिखाया कि स्पष्ट बूलियन कार्यों के लिए कई ज्ञात परिपथ निचली सीमाएं संबंधित परिपथ वर्ग के विरुद्ध तथाकथित प्राकृतिक प्रमाण के अस्तित्व का संकेत देती हैं।[17] दूसरी ओर, पी/पॉली के खिलाफ उपयोगी प्राकृतिक गुण शक्तिशाली छद्म यादृच्छिक जनरेटर को तोड़ देंगे। इसे अधिकांशतः शक्तिशाली परिपथ निचली सीमा सिद्ध करने के लिए प्राकृतिक सबूत बाधा के रूप में व्याख्या की जाती है। 2016 में, कारमोसिनो, इम्पैग्लियाज़ो, कबनेट्स और कोलोकोलोवा ने सिद्ध कर दिया कि कुशल शिक्षण एल्गोरिदम के निर्माण के लिए प्राकृतिक गुणों का भी उपयोग किया जा सकता है।[18]
जटिलता वर्ग
कई परिपथ जटिलता वर्गों को वर्ग पदानुक्रमों के संदर्भ में परिभाषित किया गया है। प्रत्येक गैर-ऋणात्मक पूर्णांक i के लिए, वर्ग NC (जटिलता)|NC होता हैi, जिसमें गहराई के बहुपद-आकार के परिपथ सम्मिलित हैं , बाउंडेड फैन-इन एंड, और, और नॉट गेट्स का उपयोग करना। इन सभी वर्गों की संघ एनसी चर्चा का विषय है। असीमित फैन-इन गेट्स पर विचार करके, कक्षाएं एसी (जटिलता) | एसीi और AC (जो NC के बराबर है) की रचना की जा सकती है। गेट्स के विभिन्न समुच्चयों की अनुमति देकर ही आकार और गहराई प्रतिबंधों के साथ कई अन्य परिपथ जटिलता वर्गों का निर्माण किया जा सकता है।
समय जटिलता से संबंध
यदि कोई निश्चित भाषा, , कॉम्प्लेक्सिटी क्लास | टाइम-कॉम्प्लेक्सिटी क्लास से संबंधित है किसी समारोह के लिए , तब परिपथ जटिलता है . यदि भाषा को स्वीकार करने वाली ट्यूरिंग मशीन ट्यूरिंग मशीन समकक्ष है (जिसका अर्थ है कि यह इनपुट की परवाह किए बिना समान मेमोरी सेल को पढ़ती और लिखती है), तो परिपथ जटिलता है .[19]
यह भी देखें
टिप्पणियाँ
संदर्भ
- ↑ Sipser, Michael (1997). Introduction to the theory of computation (1 ed.). Boston, USA: PWS Publishing Company. p. 324.
- ↑ Shannon, Claude Elwood (1949). "The synthesis of two-terminal switching circuits". Bell System Technical Journal. 28 (1): 59–98. doi:10.1002/j.1538-7305.1949.tb03624.x.
- ↑ 3.0 3.1 Ajtai, Miklós (1983). "-formulae on finite structures". Annals of Pure and Applied Logic. 24: 1–24. doi:10.1016/0168-0072(83)90038-6.
- ↑ 4.0 4.1 Ajtai, Miklós; Komlós, János; Szemerédi, Endre (1983). An 0(n log n) sorting network. pp. 1–9. ISBN 978-0-89791-099-6.
{{cite book}}:|journal=ignored (help) - ↑ 5.0 5.1 Furst, Merrick L.; Saxe, James Benjamin; Sipser, Michael Fredric (1984). "Parity, circuits, and the polynomial-time hierarchy". Mathematical Systems Theory. 17 (1): 13–27. doi:10.1007/BF01744431. MR 0738749.
- ↑ Håstad, Johan Torkel (1987). Computational limitations of small depth circuits (PDF) (Ph.D. thesis). Massachusetts Institute of Technology.
- ↑ 7.0 7.1 Razborov, Aleksandr Aleksandrovich (1985). "Lower bounds on the monotone complexity of some Boolean functions". Soviet Mathematics - Doklady. 31: 354–357. ISSN 0197-6788.
- ↑ Smolensky, Roman (1987). "Algebraic methods in the theory of lower bounds for Boolean circuit complexity". Proceedings of the 19th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery. pp. 77–82. doi:10.1145/28395.28404.
- ↑ Alon, Noga; Boppana, Ravi B. (1987). "The monotone circuit complexity of Boolean functions". Combinatorica. 7 (1): 1–22. CiteSeerX 10.1.1.300.9623. doi:10.1007/bf02579196.
- ↑ Rossman, Benjamin E. (2008). "On the constant-depth complexity of k-clique". STOC 2008: Proceedings of the 40th annual ACM symposium on Theory of computing. Association for Computing Machinery. pp. 721–730. doi:10.1145/1374376.1374480.
- ↑ Raz, Ran; McKenzie, Pierre (1999). "Separation of the monotone NC hierarchy". Combinatorica. 19 (3): 403–435. doi:10.1007/s004930050062.
- ↑ Hesse, William (2001). "Division is in uniform TC0". Proceedings of the 28th International Colloquium on Automata, Languages and Programming. Springer Verlag. pp. 104–114.
- ↑ Allender, Eric Warren, ed. (1997). "Circuit Complexity before the Dawn of the New Millennium" (PDF). [1] (NB. A 1997 survey of the field by Eric Allender.)
- ↑ Santhanam, Rahul (2007). "Circuit lower bounds for Merlin-Arthur classes". STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. pp. 275–283. CiteSeerX 10.1.1.92.4422. doi:10.1145/1250790.1250832.
- ↑ Williams, Richard Ryan (2011). "Non-Uniform ACC Circuit Lower Bounds" (PDF). CCC 2011: Proceedings of the 26th Annual IEEE Conference on Computational Complexity. pp. 115–125. doi:10.1109/CCC.2011.36.
- ↑ Kabanets, Valentine [at Wikidata]; Impagliazzo, Russell Graham (2004). "Derandomizing polynomial identity tests means proving circuit lower bounds". Computational Complexity. 13 (1): 1–46. doi:10.1007/s00037-004-0182-6.
- ↑ Razborov, Aleksandr Aleksandrovich; Rudich, Steven (1997). "Natural proofs". Journal of Computer and System Sciences. Vol. 55. pp. 24–35.
- ↑ Carmosino, Marco; Impagliazzo, Russell Graham; Kabanets, Valentine [at Wikidata]; Kolokolova, Antonina (2016). "Learning algorithms from natural proofs". Computational Complexity Conference.
- ↑ Pippenger, Nicholas; Fischer, Michael J. (1979), "Relations Among Complexity Measures", Journal of the ACM, 26 (3): 361–381, doi:10.1145/322123.322138
अग्रिम पठन
- Vollmer, Heribert [in Deutsch] (1999). Introduction to Circuit Complexity: a Uniform Approach. Texts in Theoretical Computer Science. An EATCS Series. Springer Verlag. ISBN 978-3-540-64310-4.
- Wegener, Ingo (1987) [November 1986]. The Complexity of Boolean Functions. Wiley–Teubner Series in Computer Sciences. Frankfurt am Main/Bielefeld, Germany: John Wiley & Sons Ltd., and B. G. Teubner Verlag, Stuttgart. ISBN 3-519-02107-2. LCCN 87-10388. (xii+457 pages) (NB. At the time an influential textbook on the subject, commonly known as the "Blue Book". Also available for download (PDF) at the Electronic Colloquium on Computational Complexity.)
- Zwick, Uri. "Lecture notes for a course of Uri Zwick on circuit complexity".
