बूलियन परिपथ: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Model of computation}} | {{Short description|Model of computation}} | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत]] और [[सर्किट जटिलता|परिपथ जटिलता]] में, बूलियन परिपथ [[संयोजन तर्क]] [[डिजिटल इलेक्ट्रॉनिक्स|डिजिटल विद्युत]] के लिए | [[कम्प्यूटेशनल जटिलता सिद्धांत]] और [[सर्किट जटिलता|परिपथ जटिलता]] में, बूलियन परिपथ [[संयोजन तर्क]] [[डिजिटल इलेक्ट्रॉनिक्स|डिजिटल विद्युत]] के लिए गणितीय मॉडल है। बूलियन परिपथ के परिवार द्वारा [[औपचारिक भाषा]] तय की जा सकती है, प्रत्येक संभावित इनपुट लंबाई के लिए परिपथ। | ||
बूलियन परिपथ को उनके पास उपस्थित [[तर्क द्वार| | बूलियन परिपथ को उनके पास उपस्थित [[तर्क द्वार|लॉजिक]] गेट्स के संदर्भ में परिभाषित किया गया है। उदाहरण के लिए,परिपथ में [[बाइनरी फ़ंक्शन]] एंड और और गेट्स और [[एकात्मक ऑपरेशन]] नॉट गेट्स हो सकते हैं, या पूरी तरह से बाइनरी नेंड गेट्स द्वारा वर्णित हो सकते हैं। प्रत्येक गेट कुछ [[बूलियन समारोह]] से मेल खाता है जो इनपुट के रूप में [[अंश]] की निश्चित संख्या लेता है और बिट को आउटपुट करता है। | ||
बूलियन परिपथ [[कंप्यूटर इंजीनियरिंग]] में उपयोग किए जाने वाले कई डिजिटल घटकों के | बूलियन परिपथ [[कंप्यूटर इंजीनियरिंग]] में उपयोग किए जाने वाले कई डिजिटल घटकों के लिए मॉडल प्रदान करते हैं, जिसमें [[बहुसंकेतक]], [[योजक (इलेक्ट्रॉनिक्स)|योजक (विद्युत)]] और अंकगणितीय तर्क इकाइयां सम्मिलित हैं, किन्तु वे [[अनुक्रमिक तर्क]] को बाहर करते हैं। वे अमूर्त हैं जो वास्तविक डिजिटल लॉजिक परिपथ को डिजाइन करने के लिए प्रासंगिक कई पहलुओं को छोड़ देते हैं, जैसे कि [[मेटास्टेबिलिटी (इलेक्ट्रॉनिक्स)|मेटास्टेबिलिटी (विद्युत)]], [[प्रशंसक बाहर]], [[खतरा (तर्क)]], [[शक्ति अनुकूलन (EDA)|शक्ति अनुकूलन (ईडीए)]] ईडीए), और प्रसार विलंब परिवर्तनशीलता। | ||
== औपचारिक परिभाषा == | == औपचारिक परिभाषा == | ||
बूलियन परिपथ | बूलियन परिपथ की औपचारिक परिभाषा देने में, [[हर्बर्ट वोल्मर]] परिपथ मॉडल में स्वीकार्य गेट्स के अनुरूप बूलियन फ़ंक्शंस के सेट बी के रूप में आधार को परिभाषित करके प्रारंभिकू करते हैं। आधार बी पर बूलियन परिपथ, एन इनपुट और एम आउटपुट के साथ, फिर परिमित निर्देशित चक्रीय ग्राफ के रूप में परिभाषित किया जाता है। प्रत्येक वर्टेक्स या तो आधार फ़ंक्शन या इनपुट में से से मेल खाता है, और बिल्कुल एम नोड्स का सेट होता है जिसे आउटपुट के रूप में लेबल किया जाता है।<ref name=Vollmer>{{cite book | last = Vollmer | first = Heribert | title = Introduction to Circuit Complexity | year = 1999 | publisher = Springer | location = Berlin | isbn = 3-540-64310-9 }}</ref>{{rp|8}} एक ही बूलियन फ़ंक्शन के विभिन्न तर्कों के बीच अंतर करने के लिए किनारों में कुछ आदेश भी होना चाहिए।<ref name=Vollmer/>{{rp|9}} | ||
एक विशेष स्थितियों के रूप में, | एक विशेष स्थितियों के रूप में, [[प्रस्तावक सूत्र]] या [[बूलियन अभिव्यक्ति]] एकल आउटपुट नोड वाला बूलियन परिपथ है जिसमें हर दूसरे नोड का [[प्रशंसक बाहर]] 1 होता है। . | ||
बूलियन परिपथ के | बूलियन परिपथ के लिए सामान्य आधार सेट {एंड गेट, और गेट, नॉट गेट} है, जो [[कार्यात्मक पूर्णता]] है, i। इ। जिससे अन्य सभी बूलियन कार्यों का निर्माण किया जा सकता है। | ||
== कम्प्यूटेशनल जटिलता == | == कम्प्यूटेशनल जटिलता == | ||
=== पृष्ठभूमि === | === पृष्ठभूमि === | ||
एक विशेष परिपथ निश्चित आकार के इनपुट पर ही कार्य करता है। यद्यपि, औपचारिक भाषाएँ ([[स्ट्रिंग (कंप्यूटर विज्ञान)]] | [[निर्णय समस्या]]ओं के स्ट्रिंग-आधारित प्रतिनिधित्व) में विभिन्न लंबाई के तार होते हैं, इसलिए भाषाओं | एक विशेष परिपथ निश्चित आकार के इनपुट पर ही कार्य करता है। यद्यपि, औपचारिक भाषाएँ ([[स्ट्रिंग (कंप्यूटर विज्ञान)]] | [[निर्णय समस्या]]ओं के स्ट्रिंग-आधारित प्रतिनिधित्व) में विभिन्न लंबाई के तार होते हैं, इसलिए भाषाओं को परिपथ द्वारा पूरी तरह से कैप्चर नहीं किया जा सकता है (ट्यूरिंग मशीन मॉडल के विपरीत, जिसमें भाषा है पूरी तरह से ट्यूरिंग मशीन द्वारा वर्णित)। के अतिरिक्त परिपथ परिवार द्वारा भाषा का प्रतिनिधित्व किया जाता है। परिपथ परिवार परिपथ की अनंत सूची है <math>(C_0,C_1,C_2,...)</math>, जहाँ <math>C_n</math> है <math>n</math> इनपुट चर। कहा जाता है कि परिपथ परिवार भाषा तय करता है <math>L</math> यदि, हर स्ट्रिंग के लिए <math>w</math>, <math>w</math> भाषा में है <math>L</math> यदि और केवल यदि <math>C_n(w)=1</math>, जहाँ <math>n</math> की लम्बाई है <math>w</math>. दूसरे शब्दों में, भाषा तारों का समूह है, जो परिपथ पर प्रयुक्त होने पर उनकी लंबाई के अनुरूप होती है, जो 1 का मूल्यांकन करती है।<ref name=Sipser>{{cite book|last=Sipser|first=Michael|author-link=Michael Sipser|title=Introduction to the Theory of Computation|edition=2nd|year=2006|publisher=Thomson Course Technology|location=USA|isbn=978-0-534-95097-2|title-link=Introduction to the Theory of Computation}}</ref>{{rp|354}} | ||
| Line 24: | Line 24: | ||
कई महत्वपूर्ण कम्प्यूटेशनल जटिलता सिद्धांत को बूलियन परिपथ पर परिभाषित किया जा सकता है, जिसमें परिपथ की गहराई, परिपथ का आकार और एंड गेट्स और और गेट्स के बीच विकल्पों की संख्या सम्मिलित है। उदाहरण के लिए, बूलियन परिपथ की आकार जटिलता परिपथ में फाटकों की संख्या है। | कई महत्वपूर्ण कम्प्यूटेशनल जटिलता सिद्धांत को बूलियन परिपथ पर परिभाषित किया जा सकता है, जिसमें परिपथ की गहराई, परिपथ का आकार और एंड गेट्स और और गेट्स के बीच विकल्पों की संख्या सम्मिलित है। उदाहरण के लिए, बूलियन परिपथ की आकार जटिलता परिपथ में फाटकों की संख्या है। | ||
परिपथ के आकार की जटिलता और समय की जटिलता के | परिपथ के आकार की जटिलता और समय की जटिलता के बीच स्वाभाविक संबंध है।<ref name=Sipser/>{{rp|355}} सहज रूप से, कम समय की जटिलता वाली भाषा (अर्थात, [[ट्यूरिंग मशीन]] पर अपेक्षाकृत कुछ अनुक्रमिक संचालन की आवश्यकता होती है), इसमें छोटी परिपथ जटिलता भी होती है (अर्थात, अपेक्षाकृत कुछ बूलियन संचालन की आवश्यकता होती है)। औपचारिक रूप से, यह दिखाया जा सकता है कि यदि कोई भाषा में है <math>\mathsf{TIME}(t(n))</math>, जहाँ <math>t</math> कार्य है <math>t:\mathbb{N} \to \mathbb{N}</math>, तो इसमें परिपथ जटिलता है <math>O(t^2(n))</math>. | ||
=== जटिलता वर्ग === | === जटिलता वर्ग === | ||
| Line 30: | Line 30: | ||
बूलियन परिपथ के संदर्भ में कई महत्वपूर्ण जटिलता वर्गों को परिभाषित किया गया है। इनमें से सबसे सामान्य है पी/पॉली, भाषाओं का वह समूह जो बहुपद-आकार के परिपथ परिवारों द्वारा तय किया जा सकता है। यह सीधे इस तथ्य से अनुसरण करता है कि भाषाओं में <math>\mathsf{TIME}(t(n))</math> परिपथ जटिलता है <math>O(t^2(n))</math> वह [[पी (जटिलता)]]<math>\subseteq</math>पी/पॉली। दूसरे शब्दों में, नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद समय में गणना की जा सकने वाली किसी भी समस्या की गणना बहुपद-आकार के परिपथ परिवार द्वारा भी की जा सकती है। आगे यह स्थितिया है कि समावेशन उचित है (अर्थात पी<math>\subsetneq</math>पी/पॉली) क्योंकि ऐसी अनिर्णीत समस्याएं हैं जो पी/पॉली में हैं। पी/पॉली में कई गुण हैं जो इसे जटिलता वर्गों के बीच संबंधों के अध्ययन में अत्यधिक उपयोगी बनाते हैं। विशेष रूप से, यह पी बनाम एनपी से संबंधित समस्याओं की जाँच करने में सहायक है। उदाहरण के लिए, यदि एनपी में कोई ऐसी भाषा है जो पी/पॉली में नहीं है तो पी<math>\neq</math>ई.जी.<ref name="arorabarak">{{cite book |last1=Arora |first1=Sanjeev |last2=Barak |first2=Boaz |title=Computational Complexity: A Modern Approach |date=2009 |publisher=Cambridge University Press |isbn=978-0-521-42426-4}}</ref>{{rp|286}} पी/पॉली [[बहुपद पदानुक्रम]] के गुणों की जांच करने में भी सहायता करता है। उदाहरण के लिए, यदि [[एनपी (जटिलता)]] ⊆ पी/पॉली, तो पीएच गिर जाता है <math>\Sigma_2^{\mathsf P}</math>. पी/पॉली और अन्य जटिलता वर्गों के बीच संबंधों का पूरा विवरण पी/पॉली या पी/पॉली का महत्व|पी/पॉली का महत्व पर उपलब्ध है। पी / पॉली में रोचक विशेषता यह भी है कि इसे बहुपद-समय ट्यूरिंग मशीन द्वारा बहुपद-सीमित [[सलाह (जटिलता)]] के साथ मान्यता प्राप्त भाषाओं के वर्ग के रूप में समान रूप से परिभाषित किया जा सकता है। | बूलियन परिपथ के संदर्भ में कई महत्वपूर्ण जटिलता वर्गों को परिभाषित किया गया है। इनमें से सबसे सामान्य है पी/पॉली, भाषाओं का वह समूह जो बहुपद-आकार के परिपथ परिवारों द्वारा तय किया जा सकता है। यह सीधे इस तथ्य से अनुसरण करता है कि भाषाओं में <math>\mathsf{TIME}(t(n))</math> परिपथ जटिलता है <math>O(t^2(n))</math> वह [[पी (जटिलता)]]<math>\subseteq</math>पी/पॉली। दूसरे शब्दों में, नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद समय में गणना की जा सकने वाली किसी भी समस्या की गणना बहुपद-आकार के परिपथ परिवार द्वारा भी की जा सकती है। आगे यह स्थितिया है कि समावेशन उचित है (अर्थात पी<math>\subsetneq</math>पी/पॉली) क्योंकि ऐसी अनिर्णीत समस्याएं हैं जो पी/पॉली में हैं। पी/पॉली में कई गुण हैं जो इसे जटिलता वर्गों के बीच संबंधों के अध्ययन में अत्यधिक उपयोगी बनाते हैं। विशेष रूप से, यह पी बनाम एनपी से संबंधित समस्याओं की जाँच करने में सहायक है। उदाहरण के लिए, यदि एनपी में कोई ऐसी भाषा है जो पी/पॉली में नहीं है तो पी<math>\neq</math>ई.जी.<ref name="arorabarak">{{cite book |last1=Arora |first1=Sanjeev |last2=Barak |first2=Boaz |title=Computational Complexity: A Modern Approach |date=2009 |publisher=Cambridge University Press |isbn=978-0-521-42426-4}}</ref>{{rp|286}} पी/पॉली [[बहुपद पदानुक्रम]] के गुणों की जांच करने में भी सहायता करता है। उदाहरण के लिए, यदि [[एनपी (जटिलता)]] ⊆ पी/पॉली, तो पीएच गिर जाता है <math>\Sigma_2^{\mathsf P}</math>. पी/पॉली और अन्य जटिलता वर्गों के बीच संबंधों का पूरा विवरण पी/पॉली या पी/पॉली का महत्व|पी/पॉली का महत्व पर उपलब्ध है। पी / पॉली में रोचक विशेषता यह भी है कि इसे बहुपद-समय ट्यूरिंग मशीन द्वारा बहुपद-सीमित [[सलाह (जटिलता)]] के साथ मान्यता प्राप्त भाषाओं के वर्ग के रूप में समान रूप से परिभाषित किया जा सकता है। | ||
पी/पॉली के दो उपवर्ग जिनके अपने आप में रोचक गुण हैं, एनसी (जटिलता) और [[एसी (जटिलता)]] हैं। इन वर्गों को न केवल उनके परिपथ आकार के संदर्भ में बल्कि उनकी गहराई के संदर्भ में भी परिभाषित किया गया | पी/पॉली के दो उपवर्ग जिनके अपने आप में रोचक गुण हैं, एनसी (जटिलता) और [[एसी (जटिलता)]] हैं। इन वर्गों को न केवल उनके परिपथ आकार के संदर्भ में बल्कि उनकी गहराई के संदर्भ में भी परिभाषित किया गया है। परिपथ की गहराई इनपुट नोड से आउटपुट नोड तक सबसे लंबे [[निर्देशित पथ]] की लंबाई है। वर्ग एनसी भाषाओं का समूह है जिसे परिपथ परिवारों द्वारा हल किया जा सकता है जो न केवल बहुपद-आकार तक ही सीमित हैं बल्कि बहुलगणकीय गहराई तक भी सीमित हैं। क्लास एसी को एनसी के समान परिभाषित किया गया है, चूंकि गेट्स को अनबाउंड फैन-इन (अर्थात एंड और और गेट्स को दो से अधिक बिट्स पर प्रयुक्त किया जा सकता है) की अनुमति है। नेकां महत्वपूर्ण वर्ग है क्योंकि यह पता चला है कि यह उन भाषाओं के वर्ग का प्रतिनिधित्व करता है जिनमें कुशल समांतर एल्गोरिदम हैं। | ||
=== परिपथ मूल्यांकन === | === परिपथ मूल्यांकन === | ||
[[सर्किट वैल्यू प्रॉब्लम|परिपथ वैल्यू प्रॉब्लम]] - दिए गए इनपुट [[बाइनरी स्ट्रिंग]] पर दिए गए बूलियन परिपथ के आउटपुट की गणना करने की समस्या - | [[सर्किट वैल्यू प्रॉब्लम|परिपथ वैल्यू प्रॉब्लम]] - दिए गए इनपुट [[बाइनरी स्ट्रिंग]] पर दिए गए बूलियन परिपथ के आउटपुट की गणना करने की समस्या - [[पी-पूर्ण]] निर्णय समस्या है।<ref name="arorabarak"/>{{rp|119}} इसलिए, इस समस्या को इस अर्थ में स्वाभाविक रूप से अनुक्रमिक माना जाता है कि समस्या को हल करने वाला कोई कुशल, अत्यधिक समानांतर एल्गोरिदम नहीं है। | ||
=== पूर्णता === | === पूर्णता === | ||
लॉजिक परिपथ सरल लॉजिक ऑपरेशंस, एंड, और और नॉट (और उनके संयोजन, जैसे गैर-अनुक्रमिक फ्लिप-फ्लॉप या परिपथ नेटवर्क) का भौतिक प्रतिनिधित्व करते हैं, जो गणितीय संरचना बनाते हैं जिसे [[बूलियन बीजगणित]] के रूप में जाना जाता है। वे इस मायने में पूर्ण हैं कि वे कोई भी नियतात्मक एल्गोरिथम निष्पादित कर सकते हैं। यद्यपि, ऐसा होता है कि यह सब कुछ नहीं है। भौतिक विश्व में हम यादृच्छिकता का भी सामना करते हैं, परिमाणीकरण प्रभावों द्वारा नियंत्रित छोटी प्रणालियों में उल्लेखनीय है, जिसे क्वांटम यांत्रिकी के सिद्धांत द्वारा वर्णित किया गया है। लॉजिक परिपथ किसी भी यादृच्छिकता का उत्पादन नहीं कर सकते हैं, और इस अर्थ में | लॉजिक परिपथ सरल लॉजिक ऑपरेशंस, एंड, और और नॉट (और उनके संयोजन, जैसे गैर-अनुक्रमिक फ्लिप-फ्लॉप या परिपथ नेटवर्क) का भौतिक प्रतिनिधित्व करते हैं, जो गणितीय संरचना बनाते हैं जिसे [[बूलियन बीजगणित]] के रूप में जाना जाता है। वे इस मायने में पूर्ण हैं कि वे कोई भी नियतात्मक एल्गोरिथम निष्पादित कर सकते हैं। यद्यपि, ऐसा होता है कि यह सब कुछ नहीं है। भौतिक विश्व में हम यादृच्छिकता का भी सामना करते हैं, परिमाणीकरण प्रभावों द्वारा नियंत्रित छोटी प्रणालियों में उल्लेखनीय है, जिसे क्वांटम यांत्रिकी के सिद्धांत द्वारा वर्णित किया गया है। लॉजिक परिपथ किसी भी यादृच्छिकता का उत्पादन नहीं कर सकते हैं, और इस अर्थ में वे अपूर्ण लॉजिक सेट बनाते हैं। इसका उपाय तर्क नेटवर्क, या कंप्यूटर, जैसे कि [[संभाव्य ट्यूरिंग मशीन]] में तदर्थ यादृच्छिक बिट जनरेटर को जोड़ने में पाया जाता है। हालिया काम<ref>{{cite journal |last1=Stipčević |first1=Mario |last2=Batelić |first2=Mateja |title=Entropy considerations in improved circuits for a biologically-inspired random pulse computer |journal=Scientific Reports |volume=12 |page=115 |year=2022 |doi=10.1038/s41598-021-04177-9|doi-access=free }}</ref> रैंडम फ्लिप-फ्लॉप नामक अंतर्निहित यादृच्छिक लॉजिक परिपथ की सैद्धांतिक अवधारणा प्रस्तुत की है, जो सेट को पूरा करती है। यह आसानी से यादृच्छिकता को पैक करता है और नियतात्मक बूलियन लॉजिक परिपथ के साथ इंटर-ऑपरेबल है। चूंकि, बूलियन बीजगणित के समकक्ष बीजगणितीय संरचना और विस्तारित सेट के लिए परिपथ निर्माण और कटौती के संबंधित विधि अभी तक अज्ञात हैं। | ||
== यह भी देखें == | == यह भी देखें == | ||
Revision as of 23:06, 22 February 2023
कम्प्यूटेशनल जटिलता सिद्धांत और परिपथ जटिलता में, बूलियन परिपथ संयोजन तर्क डिजिटल विद्युत के लिए गणितीय मॉडल है। बूलियन परिपथ के परिवार द्वारा औपचारिक भाषा तय की जा सकती है, प्रत्येक संभावित इनपुट लंबाई के लिए परिपथ।
बूलियन परिपथ को उनके पास उपस्थित लॉजिक गेट्स के संदर्भ में परिभाषित किया गया है। उदाहरण के लिए,परिपथ में बाइनरी फ़ंक्शन एंड और और गेट्स और एकात्मक ऑपरेशन नॉट गेट्स हो सकते हैं, या पूरी तरह से बाइनरी नेंड गेट्स द्वारा वर्णित हो सकते हैं। प्रत्येक गेट कुछ बूलियन समारोह से मेल खाता है जो इनपुट के रूप में अंश की निश्चित संख्या लेता है और बिट को आउटपुट करता है।
बूलियन परिपथ कंप्यूटर इंजीनियरिंग में उपयोग किए जाने वाले कई डिजिटल घटकों के लिए मॉडल प्रदान करते हैं, जिसमें बहुसंकेतक, योजक (विद्युत) और अंकगणितीय तर्क इकाइयां सम्मिलित हैं, किन्तु वे अनुक्रमिक तर्क को बाहर करते हैं। वे अमूर्त हैं जो वास्तविक डिजिटल लॉजिक परिपथ को डिजाइन करने के लिए प्रासंगिक कई पहलुओं को छोड़ देते हैं, जैसे कि मेटास्टेबिलिटी (विद्युत), प्रशंसक बाहर, खतरा (तर्क), शक्ति अनुकूलन (ईडीए) ईडीए), और प्रसार विलंब परिवर्तनशीलता।
औपचारिक परिभाषा
बूलियन परिपथ की औपचारिक परिभाषा देने में, हर्बर्ट वोल्मर परिपथ मॉडल में स्वीकार्य गेट्स के अनुरूप बूलियन फ़ंक्शंस के सेट बी के रूप में आधार को परिभाषित करके प्रारंभिकू करते हैं। आधार बी पर बूलियन परिपथ, एन इनपुट और एम आउटपुट के साथ, फिर परिमित निर्देशित चक्रीय ग्राफ के रूप में परिभाषित किया जाता है। प्रत्येक वर्टेक्स या तो आधार फ़ंक्शन या इनपुट में से से मेल खाता है, और बिल्कुल एम नोड्स का सेट होता है जिसे आउटपुट के रूप में लेबल किया जाता है।[1]: 8 एक ही बूलियन फ़ंक्शन के विभिन्न तर्कों के बीच अंतर करने के लिए किनारों में कुछ आदेश भी होना चाहिए।[1]: 9
एक विशेष स्थितियों के रूप में, प्रस्तावक सूत्र या बूलियन अभिव्यक्ति एकल आउटपुट नोड वाला बूलियन परिपथ है जिसमें हर दूसरे नोड का प्रशंसक बाहर 1 होता है। .
बूलियन परिपथ के लिए सामान्य आधार सेट {एंड गेट, और गेट, नॉट गेट} है, जो कार्यात्मक पूर्णता है, i। इ। जिससे अन्य सभी बूलियन कार्यों का निर्माण किया जा सकता है।
कम्प्यूटेशनल जटिलता
पृष्ठभूमि
एक विशेष परिपथ निश्चित आकार के इनपुट पर ही कार्य करता है। यद्यपि, औपचारिक भाषाएँ (स्ट्रिंग (कंप्यूटर विज्ञान) | निर्णय समस्याओं के स्ट्रिंग-आधारित प्रतिनिधित्व) में विभिन्न लंबाई के तार होते हैं, इसलिए भाषाओं को परिपथ द्वारा पूरी तरह से कैप्चर नहीं किया जा सकता है (ट्यूरिंग मशीन मॉडल के विपरीत, जिसमें भाषा है पूरी तरह से ट्यूरिंग मशीन द्वारा वर्णित)। के अतिरिक्त परिपथ परिवार द्वारा भाषा का प्रतिनिधित्व किया जाता है। परिपथ परिवार परिपथ की अनंत सूची है , जहाँ है इनपुट चर। कहा जाता है कि परिपथ परिवार भाषा तय करता है यदि, हर स्ट्रिंग के लिए , भाषा में है यदि और केवल यदि , जहाँ की लम्बाई है . दूसरे शब्दों में, भाषा तारों का समूह है, जो परिपथ पर प्रयुक्त होने पर उनकी लंबाई के अनुरूप होती है, जो 1 का मूल्यांकन करती है।[2]: 354
जटिलता उपाय
कई महत्वपूर्ण कम्प्यूटेशनल जटिलता सिद्धांत को बूलियन परिपथ पर परिभाषित किया जा सकता है, जिसमें परिपथ की गहराई, परिपथ का आकार और एंड गेट्स और और गेट्स के बीच विकल्पों की संख्या सम्मिलित है। उदाहरण के लिए, बूलियन परिपथ की आकार जटिलता परिपथ में फाटकों की संख्या है।
परिपथ के आकार की जटिलता और समय की जटिलता के बीच स्वाभाविक संबंध है।[2]: 355 सहज रूप से, कम समय की जटिलता वाली भाषा (अर्थात, ट्यूरिंग मशीन पर अपेक्षाकृत कुछ अनुक्रमिक संचालन की आवश्यकता होती है), इसमें छोटी परिपथ जटिलता भी होती है (अर्थात, अपेक्षाकृत कुछ बूलियन संचालन की आवश्यकता होती है)। औपचारिक रूप से, यह दिखाया जा सकता है कि यदि कोई भाषा में है , जहाँ कार्य है , तो इसमें परिपथ जटिलता है .
जटिलता वर्ग
बूलियन परिपथ के संदर्भ में कई महत्वपूर्ण जटिलता वर्गों को परिभाषित किया गया है। इनमें से सबसे सामान्य है पी/पॉली, भाषाओं का वह समूह जो बहुपद-आकार के परिपथ परिवारों द्वारा तय किया जा सकता है। यह सीधे इस तथ्य से अनुसरण करता है कि भाषाओं में परिपथ जटिलता है वह पी (जटिलता)पी/पॉली। दूसरे शब्दों में, नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद समय में गणना की जा सकने वाली किसी भी समस्या की गणना बहुपद-आकार के परिपथ परिवार द्वारा भी की जा सकती है। आगे यह स्थितिया है कि समावेशन उचित है (अर्थात पीपी/पॉली) क्योंकि ऐसी अनिर्णीत समस्याएं हैं जो पी/पॉली में हैं। पी/पॉली में कई गुण हैं जो इसे जटिलता वर्गों के बीच संबंधों के अध्ययन में अत्यधिक उपयोगी बनाते हैं। विशेष रूप से, यह पी बनाम एनपी से संबंधित समस्याओं की जाँच करने में सहायक है। उदाहरण के लिए, यदि एनपी में कोई ऐसी भाषा है जो पी/पॉली में नहीं है तो पीई.जी.[3]: 286 पी/पॉली बहुपद पदानुक्रम के गुणों की जांच करने में भी सहायता करता है। उदाहरण के लिए, यदि एनपी (जटिलता) ⊆ पी/पॉली, तो पीएच गिर जाता है . पी/पॉली और अन्य जटिलता वर्गों के बीच संबंधों का पूरा विवरण पी/पॉली या पी/पॉली का महत्व|पी/पॉली का महत्व पर उपलब्ध है। पी / पॉली में रोचक विशेषता यह भी है कि इसे बहुपद-समय ट्यूरिंग मशीन द्वारा बहुपद-सीमित सलाह (जटिलता) के साथ मान्यता प्राप्त भाषाओं के वर्ग के रूप में समान रूप से परिभाषित किया जा सकता है।
पी/पॉली के दो उपवर्ग जिनके अपने आप में रोचक गुण हैं, एनसी (जटिलता) और एसी (जटिलता) हैं। इन वर्गों को न केवल उनके परिपथ आकार के संदर्भ में बल्कि उनकी गहराई के संदर्भ में भी परिभाषित किया गया है। परिपथ की गहराई इनपुट नोड से आउटपुट नोड तक सबसे लंबे निर्देशित पथ की लंबाई है। वर्ग एनसी भाषाओं का समूह है जिसे परिपथ परिवारों द्वारा हल किया जा सकता है जो न केवल बहुपद-आकार तक ही सीमित हैं बल्कि बहुलगणकीय गहराई तक भी सीमित हैं। क्लास एसी को एनसी के समान परिभाषित किया गया है, चूंकि गेट्स को अनबाउंड फैन-इन (अर्थात एंड और और गेट्स को दो से अधिक बिट्स पर प्रयुक्त किया जा सकता है) की अनुमति है। नेकां महत्वपूर्ण वर्ग है क्योंकि यह पता चला है कि यह उन भाषाओं के वर्ग का प्रतिनिधित्व करता है जिनमें कुशल समांतर एल्गोरिदम हैं।
परिपथ मूल्यांकन
परिपथ वैल्यू प्रॉब्लम - दिए गए इनपुट बाइनरी स्ट्रिंग पर दिए गए बूलियन परिपथ के आउटपुट की गणना करने की समस्या - पी-पूर्ण निर्णय समस्या है।[3]: 119 इसलिए, इस समस्या को इस अर्थ में स्वाभाविक रूप से अनुक्रमिक माना जाता है कि समस्या को हल करने वाला कोई कुशल, अत्यधिक समानांतर एल्गोरिदम नहीं है।
पूर्णता
लॉजिक परिपथ सरल लॉजिक ऑपरेशंस, एंड, और और नॉट (और उनके संयोजन, जैसे गैर-अनुक्रमिक फ्लिप-फ्लॉप या परिपथ नेटवर्क) का भौतिक प्रतिनिधित्व करते हैं, जो गणितीय संरचना बनाते हैं जिसे बूलियन बीजगणित के रूप में जाना जाता है। वे इस मायने में पूर्ण हैं कि वे कोई भी नियतात्मक एल्गोरिथम निष्पादित कर सकते हैं। यद्यपि, ऐसा होता है कि यह सब कुछ नहीं है। भौतिक विश्व में हम यादृच्छिकता का भी सामना करते हैं, परिमाणीकरण प्रभावों द्वारा नियंत्रित छोटी प्रणालियों में उल्लेखनीय है, जिसे क्वांटम यांत्रिकी के सिद्धांत द्वारा वर्णित किया गया है। लॉजिक परिपथ किसी भी यादृच्छिकता का उत्पादन नहीं कर सकते हैं, और इस अर्थ में वे अपूर्ण लॉजिक सेट बनाते हैं। इसका उपाय तर्क नेटवर्क, या कंप्यूटर, जैसे कि संभाव्य ट्यूरिंग मशीन में तदर्थ यादृच्छिक बिट जनरेटर को जोड़ने में पाया जाता है। हालिया काम[4] रैंडम फ्लिप-फ्लॉप नामक अंतर्निहित यादृच्छिक लॉजिक परिपथ की सैद्धांतिक अवधारणा प्रस्तुत की है, जो सेट को पूरा करती है। यह आसानी से यादृच्छिकता को पैक करता है और नियतात्मक बूलियन लॉजिक परिपथ के साथ इंटर-ऑपरेबल है। चूंकि, बूलियन बीजगणित के समकक्ष बीजगणितीय संरचना और विस्तारित सेट के लिए परिपथ निर्माण और कटौती के संबंधित विधि अभी तक अज्ञात हैं।
यह भी देखें
- परिपथ संतुष्टि
- लॉजिक गेट
- बूलियन तर्क
- स्विचिंग लेम्मा
फुटनोट्स
- ↑ 1.0 1.1 Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 3-540-64310-9.
- ↑ 2.0 2.1 Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. ISBN 978-0-534-95097-2.
- ↑ 3.0 3.1 Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.
- ↑ Stipčević, Mario; Batelić, Mateja (2022). "Entropy considerations in improved circuits for a biologically-inspired random pulse computer". Scientific Reports. 12: 115. doi:10.1038/s41598-021-04177-9.
श्रेणी:कम्प्यूटेशनल जटिलता सिद्धांत श्रेणी:डिजिटल परिपथ श्रेणी:कंप्यूटर विज्ञान में तर्क
