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

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

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

बूलियन सर्किट के संदर्भ में परिभाषित जटिलता वर्गों में AC⁰, AC, TC⁰, NC¹, NC, और P/poly सम्मिलित हैं।

आकार और गहराई

n इनपुट बिट्स के साथ बूलियन परिपथ एक निर्देशित अचक्रीय ग्राफ है जिसमें प्रत्येक नोड (सामान्यतः इस संदर्भ में गेट्स कहा जाता है) या तो इन-डिग्री 0 का इनपुट नोड होता है जिसे किसी द्वारा लेबल किया जाता है। $n$ इनपुट बिट्स, AND गेट,OR गेट या NOT गेट। इनमें से गेट को आउटपुट गेट के रूप में नामित किया गया है। ऐसा परिपथ स्वाभाविक रूप से इसके फलन की गणना करता है $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- समरूप कहा जाता है। डीलॉगटाइम- एकरूपता की कठोर आवश्यकता एसी जैसे उथले-गहराई वाले परिपथ-वर्गों के अध्ययन में विशेष रुचि रखती है AC⁰ या TC⁰ जब कोई संसाधन सीमा निर्दिष्ट नहीं की जाती है, तो एक भाषा पुनरावर्ती होती है (यानी, ट्यूरिंग मशीन द्वारा तय की जा सकती है) अगर और केवल अगर भाषा बूलियन सर्किट के एक समान परिवार द्वारा तय की जाती है।

बहुपद-समय का समरूप

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

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

लॉगस्थान समरूप

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

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

इतिहास

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

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

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

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

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

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

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

• 1983 [3] [4] में अजताई द्वारा और साथ ही 1984 में फुर्स्ट, सक्से और सिप्सर द्वारा सिद्ध किया गया, समानता गैर-समान AC⁰में नहीं है। [5]।
• एलेंडर द्वारा प्रमाणित, वर्ग TC⁰ PP में सख्ती से निहित है।
• वर्ग S.P 2, PP[nb 1] और MA/1 (MA एक बिट सलाह के साथ) किसी स्थिर k के लिए SIZE(n^k) में नहीं हैं
• जबकि यह संदेह है कि गैर- समरूप वर्ग ACC0 में बहुमत का कार्य सम्मिलित नहीं है, यह केवल 2010 में रयान विलियम्स (कंप्यूटर वैज्ञानिक) ने सिद्ध किया था $\mathsf{N}\mathsf{E}\mathsf{X<}$