सर्किट जटिलता

[[/index.php?title=Special:MathShowImage&hash=b6252c47c600d72b4b0f484c229f580d&mode=mathml|thumb|right|उदाहरण बूलियन सर्किट। $\wedge$ h> नोड AND गेट्स हैं, द $\vee$ नोड या द्वार हैं, और $\neg$ गेट नहीं नहीं हैं|link=|alt={\displaystyle \wedge }]]सैद्धांतिक कंप्यूटर विज्ञान में, सर्किट जटिलता कम्प्यूटेशनल जटिलता सिद्धांत की शाखा है जिसमें बूलियन कार्यों को बूलियन सर्किट के आकार या गहराई के अनुसार वर्गीकृत किया जाता है जो उनकी गणना करते हैं। संबंधित धारणा पुनरावर्ती भाषा की सर्किट जटिलता है जो मशीन है जो हमेशा सर्किट के समान परिवार द्वारा रुकती है $C_{1},C_{2},\ldots$ (नीचे देखें)।

स्पष्ट बूलियन कार्यों की गणना करने वाले बूलियन सर्किट के आकार पर निचली सीमा प्रदान करना जटिलता वर्गों को अलग करने का लोकप्रिय तरीका है। उदाहरण के लिए, P/पॉली या Importance of P/पॉली सर्किट क्लास P/पॉली में बहुपद आकार के सर्किट द्वारा गणना योग्य बूलियन फ़ंक्शन होते हैं। यह साबित करना ${\mathsf {NP}}\not \subseteq {\mathsf {P/poly}}$ पी (जटिलता) और एनपी (जटिलता) को अलग करेगा (नीचे देखें)।

बूलियन सर्किट के संदर्भ में परिभाषित जटिलता वर्गों में AC0|AC शामिल हैं⁰, AC (जटिलता), TC0|TC⁰, NC1 (जटिलता)|NC¹, एनसी (जटिलता), और पी/पॉली।

आकार और गहराई

के साथ बूलियन सर्किट $n$ इनपुट अंश्स निर्देशित अचक्रीय ग्राफ है जिसमें प्रत्येक नोड (आमतौर पर इस संदर्भ में गेट्स कहा जाता है) या तो इन-डिग्री 0 का इनपुट नोड होता है जिसे किसी द्वारा लेबल किया जाता है। $n$ इनपुट बिट्स, AND गेट, OR गेट या NOT गेट। इनमें से गेट को आउटपुट गेट के रूप में नामित किया गया है। ऐसा सर्किट स्वाभाविक रूप से इसके फ़ंक्शन की गणना करता है $n$ आदानों। सर्किट का आकार इसमें शामिल फाटकों की संख्या है और इसकी गहराई इनपुट गेट से आउटपुट गेट तक पथ की अधिकतम लंबाई है।

सर्किट जटिलता की दो प्रमुख धारणाएँ हैंबूलियन फ़ंक्शन की सर्किट-आकार की जटिलता $f$ किसी भी सर्किट कंप्यूटिंग का न्यूनतम आकार है $f$. बूलियन फ़ंक्शन की सर्किट-गहराई जटिलता $f$ किसी भी सर्किट कंप्यूटिंग की न्यूनतम गहराई है $f$.

ये धारणाएं सामान्यीकृत होती हैं जब कोई किसी भाषा की सर्किट जटिलता पर विचार करता है जिसमें अलग-अलग बिट लंबाई वाले तार होते हैं, विशेष रूप से अनंत औपचारिक भाषाएं। हालाँकि, बूलियन सर्किट केवल निश्चित संख्या में इनपुट बिट्स की अनुमति देते हैं। इस प्रकार, कोई एकल बूलियन सर्किट ऐसी भाषा तय करने में सक्षम नहीं है। इस संभावना को ध्यान में रखते हुए, सर्किट के परिवारों पर विचार किया जाता है $C_{1},C_{2},\ldots$ जहां प्रत्येक $C_{n}$ आकार के इनपुट स्वीकार करता है $n$. प्रत्येक सर्किट परिवार सर्किट द्वारा स्वाभाविक रूप से भाषा उत्पन्न करेगा $C_{n}$ outputting $1$ जब लंबाई $n$ स्ट्रिंग परिवार का सदस्य है, और $0$ अन्यथा। हम कहते हैं कि सर्किट का परिवार न्यूनतम आकार का होता है यदि कोई अन्य परिवार नहीं है जो किसी भी आकार के इनपुट पर निर्णय लेता है, $n$, से छोटे आकार के सर्किट के साथ $C_{n}$ (क्रमशः गहराई न्यूनतम परिवारों के लिए)। इस प्रकार, पुनरावर्ती भाषा | गैर-पुनरावर्ती भाषाओं के लिए भी सर्किट जटिलता सार्थक है। समान परिवार की धारणा सर्किट जटिलता के वेरिएंट को पुनरावर्ती भाषाओं के एल्गोरिथ्म आधारित जटिलता उपायों से संबंधित होने में सक्षम बनाती है। हालांकि, दी गई भाषाओं को तय करने के लिए किसी भी सर्किट परिवार को कितना जटिल होना चाहिए, इस पर निचली सीमाएं खोजने में गैर-समान संस्करण सहायक होता है।

इसलिए, औपचारिक भाषा की सर्किट-आकार की जटिलता $A$ समारोह के रूप में परिभाषित किया गया है $t:\mathbb {N} \to \mathbb {N}$, जो इनपुट की थोड़ी लंबाई से संबंधित है, $n$, न्यूनतम सर्किट के सर्किट-आकार की जटिलता के लिए $C_{n}$ यह तय करता है कि उस लंबाई के इनपुट अंदर हैं या नहीं $A$. सर्किट-डेप्थ जटिलता को इसी तरह परिभाषित किया गया है।

एकरूपता

बूलियन सर्किट तथाकथित गैर-समान सार मशीन के प्रमुख उदाहरणों में से हैं, इस अर्थ में कि अलग-अलग लंबाई के इनपुट को अलग-अलग सर्किट द्वारा संसाधित किया जाता है, इसके विपरीत ट्यूरिंग मशीन जैसे समान मॉडल के विपरीत, जहां सभी संभव के लिए ही कम्प्यूटेशनल डिवाइस का उपयोग किया जाता है। इनपुट लंबाई। व्यक्तिगत कम्प्यूटेशनल समस्या इस प्रकार बूलियन सर्किट के विशेष परिवार से जुड़ी हुई है $C_{1},C_{2},\dots$ जहां प्रत्येक $C_{n}$ n बिट्स का सर्किट हैंडलिंग इनपुट है। इन परिवारों पर अक्सर एकरूपता की शर्त लगाई जाती है, जिसके लिए कुछ संभावित कम्प्यूटेशनल संसाधन | संसाधन-बद्ध ट्यूरिंग मशीन के अस्तित्व की आवश्यकता होती है, जो इनपुट एन पर, व्यक्तिगत सर्किट का विवरण तैयार करती है। $C_{n}$. जब इस ट्यूरिंग मशीन का रनिंग टाइम बहुपद n में होता है, तो सर्किट परिवार को P-वर्दी कहा जाता है। DLOGTIME- एकरूपता की कठोर आवश्यकता एसी जैसे उथले-गहराई वाले सर्किट-वर्गों के अध्ययन में विशेष रुचि रखती है⁰ या टीसी^{0</उप>। जब कोई संसाधन सीमा निर्दिष्ट नहीं की जाती है, तो भाषा पुनरावर्ती होती है (यानी, ट्यूरिंग मशीन द्वारा तय की जा सकती है) अगर और केवल अगर भाषा बूलियन सर्किट के समान परिवार द्वारा तय की जाती है।}

बहुपद-समय की वर्दी

बूलियन सर्किट का परिवार $\{C_{n}:n\in \mathbb {N} \}$ यदि नियतात्मक ट्यूरिंग मशीन M मौजूद है, तो बहुपद-समय एकसमान है, जैसे कि

• एम बहुपद समय में चलता है
• सभी के लिए $n\in \mathbb {N}$, M का विवरण आउटपुट करता है $C_{n}$ इनपुट पर $1^{n}$

लॉगस्पेस वर्दी

बूलियन सर्किट का परिवार $\{C_{n}:n\in \mathbb {N} \}$ यदि नियतात्मक ट्यूरिंग मशीन M मौजूद है, तो लॉगस्पेस एकसमान है, जैसे कि

• एम लॉगरिदमिक स्पेस में चलता है
• सभी के लिए $n\in \mathbb {N}$, M का विवरण आउटपुट करता है $C_{n}$ इनपुट पर $1^{n}$

इतिहास

1949 में सर्किट जटिलता क्लाउड शैनन के पास वापस जाती है,जिन्होंने सिद्ध किया कि n चरों पर लगभग सभी बूलियन कार्यों के लिए आकार Θ(2) के परिपथों की आवश्यकता होती है^एन/n). इस तथ्य के बावजूद, जटिलता सिद्धांतवादी अब तक किसी भी स्पष्ट कार्य के लिए सुपरलीनियर लोअर बाउंड साबित करने में असमर्थ रहे हैं।

उपयोग किए गए सर्किट के परिवार पर कुछ प्रतिबंधों के तहत सुपरपोलिनोमियल निचली सीमाएं साबित हुई हैं। पहला कार्य जिसके लिए सुपरपोलिनोमियल सर्किट निचली सीमाएँ दिखाई गई थीं, समता फ़ंक्शन था, जो इसके इनपुट बिट्स मॉड्यूलो 2 के योग की गणना करता है। तथ्य यह है कि समानता AC0|AC में समाहित नहीं है।⁰ पहली बार 1983 में अजताई द्वारा स्वतंत्र रूप से स्थापित किया गया थाऔर 1984 में फुर्स्ट, सक्से और सिप्सर द्वारा।बाद में 1987 में जोहान हास्ताद|हस्ताद द्वारा सुधार किया गयास्थापित किया गया है कि समता फ़ंक्शन की गणना करने वाले निरंतर-गहराई वाले सर्किट के किसी भी परिवार को घातीय आकार की आवश्यकता होती है। रज़बोरोव के परिणाम का विस्तार,1987 में स्मोलेंस्कीसाबित हुआ कि यह सच है भले ही सर्किट गेट्स के साथ संवर्धित हो, इसके इनपुट बिट्स मॉडुलो कुछ विषम प्राइम पी के योग की गणना करता है।

क्लिक समस्या | के-क्लिक समस्या यह तय करने के लिए है कि क्या n शिखर पर दिए गए ग्राफ में आकार के आकार का चक्कर है। स्थिरांक n और k के किसी विशेष विकल्प के लिए, ग्राफ़ को बाइनरी में एन्कोड किया जा सकता है ${n \choose 2}$ बिट्स, जो प्रत्येक संभावित किनारे के लिए इंगित करता है कि यह मौजूद है या नहीं। फिर के-क्लिक समस्या को समारोह के रूप में औपचारिक रूप दिया जाता है $f_{k}:\{0,1\}^{n \choose 2}\to \{0,1\}$ ऐसा है कि $f_{k}$ आउटपुट 1 यदि और केवल तभी जब स्ट्रिंग द्वारा एन्कोड किए गए ग्राफ़ में आकार k का समूह होता है। कार्यों का यह परिवार मोनोटोन है और इसकी गणना सर्किट के परिवार द्वारा की जा सकती है, लेकिन यह दिखाया गया है कि इसकी गणना मोनोटोन सर्किट के बहुपद-आकार के परिवार द्वारा नहीं की जा सकती है (अर्थात, AND और OR गेट वाले सर्किट लेकिन बिना निषेध के)। 1985 में अलेक्जेंडर रज़बोरोव का मूल परिणामबाद में 1987 में अलोन और बोपना द्वारा घातीय-आकार के निचले हिस्से में सुधार किया गया।2008 में, रॉसमैनने दिखाया कि AND, OR और NOT गेट्स वाले स्थिर-गहराई वाले सर्किटों के लिए आकार की आवश्यकता होती है $\Omega (n^{k/4})$ औसत मामले की जटिलता में भी के-क्लिक समस्या को हल करने के लिए। इसके अलावा, आकार का सर्किट है $n^{k/4+O(1)}$ जो गणना करता है ${\displaystyle }$