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

सैद्धांतिक कंप्यूटर विज्ञान में, परिपथ जटिलता कम्प्यूटेशनल जटिलता सिद्धांत की शाखा है जिसमें बूलियन कार्यों को बूलियन परिपथ के आकार या गहराई के अनुसार वर्गीकृत किया जाता है जो उनकी गणना करते हैं। संबंधित धारणा पुनरावर्ती भाषा की परिपथ जटिलता है जो मशीन है जो सदैव परिपथ के समान परिवार द्वारा रुकती है $C_{1},C_{2},\ldots$ (नीचे देखें)।

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

बूलियन सर्किट के संदर्भ में परिभाषित जटिलता वर्गों में एसी0, एसी, टीसी0, एनसी1, एनसी और पी/पॉली सम्मिलित हैं।

आकार और गहराई

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

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

ये धारणाएं सामान्यीकृत होती हैं जब कोई किसी भाषा की परिपथ जटिलता पर विचार करता है जिसमें अलग-अलग बिट लंबाई वाले तार होते हैं, विशेष रूप से अनंत औपचारिक भाषाएं। यद्यपि, बूलियन परिपथ केवल निश्चित संख्या में इनपुट बिट्स की अनुमति देते हैं। इस प्रकार, कोई एकल बूलियन परिपथ ऐसी भाषा तय करने में सक्षम नहीं है। इस संभावना को ध्यान में रखते हुए, परिपथ के परिवारों पर विचार किया जाता है $C_{1},C_{2},\ldots$ जहां प्रत्येक $C_{n}$ आकार के इनपुट स्वीकार करता है $n$. प्रत्येक परिपथ परिवार परिपथ द्वारा स्वाभाविक रूप से भाषा उत्पन्न करेगा $C_{n}$ आउटपुटिंग $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 का समूह होता है। कार्यों का यह परिवार मोनोटोन है और इसकी गणना परिपथ के परिवार द्वारा की जा सकती है, किन्तु यह दिखाया गया है कि इसकी गणना मोनोटोन परिपथ के बहुपद-आकार के परिवार द्वारा नहीं की जा सकती है (अर्थात, एंड और और गेट वाले परिपथ किन्तु बिना निषेध के)। 1985 में अलेक्जेंडर रज़बोरोव का मूल परिणाम बाद में 1987 में अलोन और बोपना द्वारा घातीय-आकार के निचले हिस्से में सुधार किया गया। 2008 में, रॉसमैन ने दिखाया कि एंड, औरऔर नॉटगेट्स वाले स्थिर-गहराई वाले परिपथों के लिए आकार की आवश्यकता होती है $\Omega (n^{k/4})$ औसत स्थितियोंे की जटिलता में भी के-क्लिक समस्या को हल करने के लिए। इसके अतिरिक्त, आकार का परिपथ है $n^{k/4+O(1)}$ जो गणना करता है $f_{k}$.

1999 में, घाव बार और पियरे मैकेंजी ने बाद में दिखाया कि मोनोटोन एनसी पदानुक्रम अनंत है।

पूर्णांक विभाजन समस्या एकसमान TC0|TC में निहित है^0।

परिपथ निचली सीमा

परिपथ निचली सीमाएं सामान्यतः कठिन होती हैं। ज्ञात परिणाम सम्मिलित हैं

• समता असमान AC0|AC में नहीं है⁰, अजताई द्वारा 1983 में सिद्ध किया गया साथ ही 1984 में फुर्स्ट, सक्से और सिप्सर द्वारा।* यूनिफ़ॉर्म TC0|TC⁰ पीपी (जटिलता) में सख्ती से समाहित है, जिसे एलेंडर ने सिद्ध किया है। वर्ग S2P (जटिलता)|S^P
  ₂, पीपी और एमए (जटिलता)/1 ( सलाह के साथ एमए) आकार में नहीं हैं ( एन^k) किसी भी स्थिर k के लिए।
• जबकि यह संदेह है कि गैर-वर्दी वर्ग ACC0 में बहुमत का कार्य सम्मिलित नहीं है, यह केवल 2010 में रयान विलियम्स (कंप्यूटर वैज्ञानिक) ने सिद्ध किया था ${\mathsf {NEXP}}\not \subseteq {\mathsf {ACC}}^{0}$