सर्किट जटिलता: Difference between revisions

Revision as of 22:47, 22 February 2023

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

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

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

आकार और गहराई

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

परिपथ जटिलता की दो प्रमुख धारणाएँ हैं^[1] $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 में परिपथ जटिलता क्लाउड शैनन के पास वापस जाती है,^[2]जिन्होंने सिद्ध किया कि n चरों पर लगभग सभी बूलियन कार्यों के लिए आकार Θ(2) के परिपथों की आवश्यकता होती है^एन/n). इस तथ्य के अतिरिक्त, जटिलता सिद्धांतवादी अब तक किसी भी स्पष्ट कार्य के लिए सुपरलीनियर लोअर बाउंड सिद्ध करने में असमर्थ रहे हैं।

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

क्लिक समस्या | के-क्लिक समस्या यह तय करने के लिए है कि क्या n शिखर पर दिए गए ग्राफ में आकार के आकार का चक्कर है। स्थिरांक n और k के किसी विशेष विकल्प के लिए, ग्राफ़ को बाइनरी में एन्कोड किया जा सकता है ${n \choose 2}$ बिट्स, जो प्रत्येक संभावित किनारे के लिए इंगित करता है कि यह उपस्थ है य

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Line 5: / Line 5: @@
 स्पष्ट बूलियन कार्यों की गणना करने वाले बूलियन  परिपथ के आकार पर निचली सीमा प्रदान करना जटिलता वर्गों को अलग करने का लोकप्रिय विधि है। उदाहरण के लिए, P/पॉली या इसका महत्व P/पॉली  परिपथ क्लास P/पॉली में बहुपद आकार के  परिपथ द्वारा गणना योग्य बूलियन फ़ंक्शन होते हैं। यह सिद्ध करना <math>\mathsf{NP}\not\subseteq \mathsf{P/poly}</math> [[पी (जटिलता)]] और [[एनपी (जटिलता)]] को अलग करेगा (नीचे देखें)।
-बूलियन  परिपथ के संदर्भ में परिभाषित [[जटिलता वर्ग|जटिलता]] वर्गों में AC0|AC सम्मिलित हैं<sup>0</sup>, AC (जटिलता), TC0|TC<sup>0</sup>, NC1 (जटिलता)|NC<sup>1</sup>, एनसी (जटिलता), और पी/पॉली।
+बूलियन सर्किट के संदर्भ में परिभाषित जटिलता वर्गों में एसी0, एसी, टीसी0, एनसी1, एनसी और पी/पॉली सम्मिलित हैं।
 == आकार और गहराई ==
 n इनपुट बिट्स के साथ बूलियन  परिपथ एक निर्देशित अचक्रीय ग्राफ है जिसमें प्रत्येक नोड (सामान्यतः इस संदर्भ में गेट्स कहा जाता है) या तो [[इन-डिग्री]] 0 का इनपुट नोड होता है जिसे किसी द्वारा लेबल किया जाता है। <math>n</math> इनपुट बिट्स, एंड गेट, औरगेट या नॉटगेट। इनमें से गेट को आउटपुट गेट के रूप में नामित किया गया है। ऐसा  परिपथ स्वाभाविक रूप से इसके फ़ंक्शन की गणना करता है <math>n</math> आदानों।  परिपथ का आकार इसमें सम्मिलित फाटकों की संख्या है और इसकी गहराई इनपुट गेट से आउटपुट गेट तक पथ की अधिकतम लंबाई है।
-परिपथ जटिलता की दो प्रमुख धारणाएँ हैं<ref name="Sipser_1997"/> बूलियन फ़ंक्शन की  परिपथ-आकार की जटिलता <math>f</math> किसी भी  परिपथ कंप्यूटिंग का न्यूनतम आकार है <math>f</math>. बूलियन फ़ंक्शन की  परिपथ-गहराई जटिलता <math>f</math> किसी भी  परिपथ कंप्यूटिंग की न्यूनतम गहराई है <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> (क्रमशः गहराई न्यूनतम परिवारों के लिए)। इस प्रकार, पुनरावर्ती भाषा | गैर-पुनरावर्ती भाषाओं के लिए भी  परिपथ जटिलता सार्थक है। समान परिवार की धारणा  परिपथ जटिलता के वेरिएंट को पुनरावर्ती भाषाओं के एल्गोरिथ्म आधारित जटिलता उपायों से संबंधित होने में सक्षम बनाती है। चूंकि, दी गई भाषाओं को तय करने के लिए किसी भी  परिपथ परिवार को कितना जटिल होना चाहिए, इस पर निचली सीमाएं खोजने में गैर-समान संस्करण सहायक होता है।
@@ Line 46: / Line 46: @@
 परिपथ निचली सीमाएं सामान्यतः कठिन होती हैं। ज्ञात परिणाम सम्मिलित हैं
 * समता असमान 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|ACC<sup>0</sup> में बहुमत का कार्य सम्मिलित नहीं है, यह केवल 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>  परिपथ।
@@ Line 55: / Line 55: @@
 == जटिलता वर्ग ==
-कई  परिपथ जटिलता वर्गों को वर्ग पदानुक्रमों के संदर्भ में परिभाषित किया गया है। प्रत्येक गैर-ऋणात्मक पूर्णांक i के लिए, वर्ग NC (जटिलता)|NC होता है<sup>i</sup>, जिसमें गहराई के बहुपद-आकार के  परिपथ सम्मिलित हैं <math>O(\log^i(n))</math>, बाउंडेड फैन-इन एंड, और, और नॉटगेट्स का उपयोग करना। इन सभी वर्गों की संघ एनसी चर्चा का विषय है। असीमित फैन-इन गेट्स पर विचार करके, कक्षाएं एसी (जटिलता) | एसी<sup>i</sup> और AC (जो NC के बराबर है) की रचना की जा सकती है। गेट्स के विभिन्न समुच्चयों की अनुमति देकर ही आकार और गहराई प्रतिबंधों के साथ कई अन्य  परिपथ जटिलता वर्गों का निर्माण किया जा सकता है।
+कई  परिपथ जटिलता वर्गों को वर्ग पदानुक्रमों के संदर्भ में परिभाषित किया गया है। प्रत्येक गैर-ऋणात्मक पूर्णांक i के लिए, वर्ग NC (जटिलता)|NC होता है<sup>i</sup>, जिसमें गहराई के बहुपद-आकार के  परिपथ सम्मिलित हैं <math>O(\log^i(n))</math>, बाउंडेड फैन-इन एंड, और, और नॉट गेट्स का उपयोग करना। इन सभी वर्गों की संघ एनसी चर्चा का विषय है। असीमित फैन-इन गेट्स पर विचार करके, कक्षाएं एसी (जटिलता) | एसी<sup>i</sup> और AC (जो NC के बराबर है) की रचना की जा सकती है। गेट्स के विभिन्न समुच्चयों की अनुमति देकर ही आकार और गहराई प्रतिबंधों के साथ कई अन्य  परिपथ जटिलता वर्गों का निर्माण किया जा सकता है।
 == समय जटिलता से संबंध ==

Anonymous

Search

सर्किट जटिलता: Difference between revisions

Namespaces

More

Page actions