बूलियन परिपथ: Difference between revisions

Revision as of 14:14, 24 February 2023

कम्प्यूटेशनल जटिलता सिद्धांत और परिपथ जटिलता में, बूलियन परिपथ संयोजन तर्क डिजिटल विद्युत के लिए गणितीय मॉडल है। बूलियन परिपथ के वर्ग द्वारा औपचारिक भाषा तय की जा सकती है, प्रत्येक संभावित इनपुट लंबाई के लिए परिपथ।

बूलियन परिपथ को उनके पास उपस्थित लॉजिक गेट्स के संदर्भ में परिभाषित किया गया है। उदाहरण के लिए,परिपथ में बाइनरी फलन AND और OR गेट्स और एकात्मक ऑपरेशन NOT गेट्स हो सकते हैं, या पूरी तरह से बाइनरी NAND गेट्स द्वारा वर्णित हो सकते हैं। प्रत्येक गेट कुछ बूलियन फलन से मेल खाता है जो इनपुट के रूप में अंश की निश्चित संख्या लेता है और बिट को आउटपुट करता है।

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

औपचारिक परिभाषा

बूलियन परिपथ की औपचारिक परिभाषा देने में, हर्बर्ट वोल्मर परिपथ मॉडल में स्वीकार्य गेट्स के अनुरूप बूलियन फलन के समुच्चय B के रूप में आधार को परिभाषित करके प्रारंभिकू करते हैं। आधार B पर बूलियन परिपथ, N इनपुट और M आउटपुट के साथ, फिर परिमित निर्देशित चक्रीय ग्राफ के रूप में परिभाषित किया जाता है। प्रत्येक वर्टेक्स या तो आधार फलन या इनपुट में से से मेल खाता है, और बिल्कुल M नोड्स का समुच्चय होता है जिसे आउटपुट के रूप में लेबल किया जाता है।^[1]^: 8 एक ही बूलियन फलन के विभिन्न तर्कों के बीच अंतर करने के लिए किनारों में कुछ आदेश भी होना चाहिए।^[1]^: 9

एक विशेष स्थितियों के रूप में, प्रस्तावक सूत्र या बूलियन अभिव्यक्ति एकल आउटपुट नोड वाला बूलियन परिपथ है जिसमें हर दूसरे नोड का प्रशंसक बाहर 1 होता है। .

बूलियन परिपथ के लिए सामान्य आधार समुच्चय {AND गेट, OR गेट, NOT गेट} है, जो कार्यात्मक पूर्णता है, जैसे कि जिससे अन्य सभी बूलियन कार्यों का निर्माण किया जा सकता है।

कम्प्यूटेशनल जटिलता

परिप्रेक्ष्य

एक विशेष परिपथ निश्चित आकार के इनपुट पर ही कार्य करता है। यद्यपि, औपचारिक भाषाएँ (स्ट्रिंग (कंप्यूटर विज्ञान) | निर्णय समस्याओं के स्ट्रिंग-आधारित प्रतिनिधित्व) में विभिन्न लंबाई के तार होते हैं, इसलिए भाषाओं को परिपथ द्वारा पूरी तरह से कैप्चर नहीं किया जा सकता है (ट्यूरिंग मशीन मॉडल के विपरीत, जिसमें भाषा है पूरी तरह से ट्यूरिंग मशीन द्वारा वर्णित)। के अतिरिक्त परिपथ वर्ग द्वारा भाषा का प्रतिनिधित्व किया जाता है। परिपथ वर्ग परिपथ की अनंत सूची है $(C_{0},C_{1},C_{2},...)$ , जहाँ $C_{n}$ है $n$ इनपुट चर है । एक परिपथ वर्ग को भाषा तय करने के लिए कहा जाता है $L$ यदि, हर स्ट्रिंग के लिए $w$ , $w$ भाषा में है $L$ यदि और केवल यदि $C_{n}(w)=1$ , जहाँ $n$ , $w$ की लम्बाई है . दूसरे शब्दों में, भाषा तारों का समूह है, जो परिपथ पर प्रयुक्त होने पर उनकी लंबाई के अनुरूप होती है, जो 1 का मूल्यांकन करती है।^[2]^: 354

जटिलता उपाय

कई महत्वपूर्ण कम्प्यूटेशनल जटिलता सिद्धांत को बूलियन परिपथ पर परिभाषित किया जा सकता है, जिसमें परिपथ की गहराई, परिपथ का आकार और AND गेट्स और OR गेट्स के बीच विकल्पों की संख्या सम्मिलित है। उदाहरण के लिए, बूलियन परिपथ की आकार जटिलता परिपथ में फाटकों की संख्या है।

परिपथ के आकार की जटिलता और समय की जटिलता के बीच स्वाभाविक संबंध है।^[2]^: 355 सहज रूप से, कम समय की जटिलता वाली भाषा (अर्थात, ट्यूरिंग मशीन पर अपेक्षाकृत कुछ अनुक्रमिक संचालन की आवश्यकता होती है), इसमें छोटी परिपथ जटिलता भी होती है (अर्थात, अपेक्षाकृत कुछ बूलियन संचालन की आवश्यकता होती है)। औपचारिक रूप से, यह दिखाया जा सकता है कि यदि कोई भाषा में है ${\mathsf {TIME}}(t(n))$ , जहाँ $t$ कार्य है $t:\mathbb {N} \to \mathbb {N}$ , तो इसमें परिपथ जटिलता $O(t^{2}(n))$ है.

जटिलता वर्ग

बूलियन परिपथ के संदर्भ में कई महत्वपूर्ण जटिलता वर्गों को परिभाषित किया गया है। इनमें से सबसे सामान्य है P/POLY, भाषाओं का वह समूह जो बहुपद-आकार के परिपथ वर्ग द्वारा तय किया जा सकता है। यह सीधे इस तथ्य को अनुसरण करता है कि भाषाओं में ${\mathsf {TIME}}(t(n))$ परिपथ जटिलता है $O(t^{2}(n))$ वह P $\subseteq$ P/POLY। दूसरे शब्दों में, नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद समय में गणना की जा सकने वाली किसी भी समस्या की गणना बहुपद-आकार के परिपथ वर्ग द्वारा भी की जा सकती है। आगे यह स्थितिया है कि समावेशन उचित है (अर्थात P $\subsetneq$ P/POLY) क्योंकि ऐसी अनिर्णीत समस्याएं हैं जो P/POLY में हैं। P/POLY में कई गुण हैं जो इसे जटिलता वर्गों के बीच संबंधों के अध्ययन में अत्यधिक उपयोगी बनाते हैं। विशेष रूप से, यह P बनाम NP से संबंधित समस्याओं की जाँच करने में सहायक है। उदाहरण के लिए, यदि NP में कोई ऐसी भाषा है जो P/POLY में नहीं है तो P $\neq$ NP.^[3]^: 286 P/POLY बहुपद पदानुक्रम के गुणों की जांच करने में भी सहायता करता है। उदाहरण के लिए, यदि NP⊆ P/POLY, तो पीएच गिर जाता है $\Sigma _{2}^{\mathsf {P}}$ . P/POLY और अन्य जटिलता वर्गों के बीच संबंधों का पूरा विवरण P/POLY या P/POLY का महत्व| P/POLY का महत्व पर उपलब्ध है। P/POLY में रोचक विशेषता यह भी है कि इसे बहुपद-समय ट्यूरिंग मशीन द्वारा बहुपद-सीमित सलाह (जटिलता) के साथ मान्यता प्राप्त भाषाओं के वर्ग के रूप में समान रूप से परिभाषित किया जा सकता है।

P/POLY के दो उपवर्ग जिनके अपने आप में रोचक गुण हैं, NC(जटिलता) और AC(जटिलता) हैं। इन वर्गों को न केवल उनके परिपथ आकार के संदर्भ में बल्कि उनकी गहराई के संदर्भ में भी परिभाषित किया गया है। परिपथ की गहराई इनपुट नोड से आउटपुट नोड तक सबसे लंबे निर्देशित पथ की लंबाई है। वर्ग एनसी भाषाओं का समूह है जिसे परिपथ वर्ग द्वारा हल किया जा सकता है जो न केवल बहुपद-आकार तक ही सीमित हैं बल्कि बहुलगणकीय गहराई तक भी सीमित हैं। क्लास एसी को एनसी के समान परिभाषित किया गया है, चूंकि गेट्स को अनबाउंडेड फैन-इन (अर्थात AND और OR गेट्स को दो से अधिक बिट्स पर प्रयुक्त किया जा सकता है) की अनुमति है। नेकां महत्वपूर्ण वर्ग है क्योंकि यह पता चला है कि यह उन भाषाओं के वर्ग का प्रतिनिधित्व करता है जिनमें कुशल समांतर एल्गोरिदम हैं।

परिपथ मूल्यांकन

परिपथ वैल्यू प्रॉब्लम - दिए गए इनपुट बाइनरी स्ट्रिंग पर दिए गए बूलियन परिपथ के आउटपुट की गणना करने की समस्या - P-पूर्ण निर्णय समस्या है।^[3]^: 119 इसलिए, इस समस्या को इस अर्थ में स्वाभाविक रूप से अनुक्रमिक माना जाता है कि समस्या को हल करने वाला कोई कुशल, अत्यधिक समानांतर एल्गोरिदम नहीं है।

पूर्णता

लॉजिक परिपथ सरल लॉजिक ऑपरेशंस, AND,OR और NOT (और उनके संयोजन, जैसे गैर-अनुक्रमिक फ्लिप-फ्लॉप या परिपथ नेटवर्क) का भौतिक प्रतिनिधित्व करते हैं, जो गणितीय संरचना बनाते हैं जिसे बूलियन बीजगणित के रूप में जाना जाता है। वे इस मायने में पूर्ण हैं कि वे कोई भी नियतात्मक एल्गोरिथम निष्पादित कर सकते हैं। यद्यपि, ऐसा होता है कि यह सब कुछ नहीं है। भौतिक विश्व में हम यादृच्छिकता का भी सामना करते हैं, परिमाणीकरण प्रभावों द्वारा नियंत्रित छोटी प्रणालियों में उल्लेखनीय है, जिसे मात्रा यांत्रिकी के सिद्धांत द्वारा वर्णित किया गया है। लॉजिक परिपथ किसी भी यादृच्छिकता का उत्पादन नहीं कर सकते हैं, और इस अर्थ में वे अपूर्ण लॉजिक समुच्चय बनाते हैं। इसका उपाय तर्क नेटवर्क, या कंप्यूटर, जैसे कि संभाव्य ट्यूरिंग मशीन में तदर्थ यादृच्छिक बिट जनरेटर को जोड़ने में पाया जाता है। हालिया काम^[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.

श्रेणी:कम्प्यूटेशनल जटिलता सिद्धांत श्रेणी:डिजिटल परिपथ श्रेणी:कंप्यूटर विज्ञान में तर्क

[Vollmer-1] 1.0 ^1.1 Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 3-540-64310-9.

[Sipser-2] 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.

[arorabarak-3] 3.0 ^3.1 Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.

[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.

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
 {{Short description|Model of computation}}
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] और [[सर्किट जटिलता|परिपथ जटिलता]] में, बूलियन परिपथ [[संयोजन तर्क]] [[डिजिटल इलेक्ट्रॉनिक्स|डिजिटल विद्युत]] के लिए गणितीय मॉडल है। बूलियन परिपथ के परिवार द्वारा [[औपचारिक भाषा]] तय की जा सकती है, प्रत्येक संभावित इनपुट लंबाई के लिए परिपथ।
+[[कम्प्यूटेशनल जटिलता सिद्धांत]] और [[सर्किट जटिलता|परिपथ जटिलता]] में, बूलियन परिपथ [[संयोजन तर्क]] [[डिजिटल इलेक्ट्रॉनिक्स|डिजिटल विद्युत]] के लिए गणितीय मॉडल है। बूलियन परिपथ के वर्ग द्वारा [[औपचारिक भाषा]] तय की जा सकती है, प्रत्येक संभावित इनपुट लंबाई के लिए परिपथ।
-बूलियन परिपथ को उनके पास उपस्थित [[तर्क द्वार|लॉजिक]] गेट्स के संदर्भ में परिभाषित किया गया है। उदाहरण के लिए,परिपथ में [[बाइनरी फ़ंक्शन|बाइनरी फलन]]  एंड और और गेट्स और [[एकात्मक ऑपरेशन]] नॉट गेट्स हो सकते हैं, या पूरी तरह से बाइनरी नेंड गेट्स द्वारा वर्णित हो सकते हैं। प्रत्येक गेट कुछ [[बूलियन समारोह|बूलियन फलन]]  से मेल खाता है जो इनपुट के रूप में [[अंश]] की निश्चित संख्या लेता है और बिट को आउटपुट करता है।
+बूलियन परिपथ को उनके पास उपस्थित [[तर्क द्वार|लॉजिक]] गेट्स के संदर्भ में परिभाषित किया गया है। उदाहरण के लिए,परिपथ में [[बाइनरी फ़ंक्शन|बाइनरी फलन]]  AND और OR गेट्स और [[एकात्मक ऑपरेशन]] NOT गेट्स हो सकते हैं, या पूरी तरह से बाइनरी NAND गेट्स द्वारा वर्णित हो सकते हैं। प्रत्येक गेट कुछ [[बूलियन समारोह|बूलियन फलन]]  से मेल खाता है जो इनपुट के रूप में [[अंश]] की निश्चित संख्या लेता है और बिट को आउटपुट करता है।
-बूलियन परिपथ [[कंप्यूटर इंजीनियरिंग]] में उपयोग किए जाने वाले कई डिजिटल घटकों के लिए मॉडल प्रदान करते हैं, जिसमें [[बहुसंकेतक]], [[योजक (इलेक्ट्रॉनिक्स)|योजक (विद्युत)]] और अंकगणितीय तर्क इकाइयां सम्मिलित हैं, किन्तु वे [[अनुक्रमिक तर्क]] को बाहर करते हैं। वे अमूर्त हैं जो वास्तविक डिजिटल लॉजिक परिपथ को डिजाइन करने के लिए प्रासंगिक कई पहलुओं को छोड़ देते हैं, जैसे कि [[मेटास्टेबिलिटी (इलेक्ट्रॉनिक्स)|मेटास्टेबिलिटी (विद्युत)]], [[प्रशंसक बाहर]], [[खतरा (तर्क)]], [[शक्ति अनुकूलन (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}}
+बूलियन परिपथ की औपचारिक परिभाषा देने में, [[हर्बर्ट वोल्मर]] परिपथ मॉडल में स्वीकार्य गेट्स के अनुरूप बूलियन फलन के समुच्चय B के रूप में आधार को परिभाषित करके प्रारंभिकू करते हैं। आधार B पर बूलियन परिपथ, N इनपुट और M आउटपुट के साथ, फिर परिमित निर्देशित चक्रीय ग्राफ के रूप में परिभाषित किया जाता है। प्रत्येक वर्टेक्स या तो आधार फलन या इनपुट में से से मेल खाता है, और बिल्कुल M नोड्स का समुच्चय होता है जिसे आउटपुट के रूप में लेबल किया जाता है।<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। इ। जिससे अन्य सभी बूलियन कार्यों का निर्माण किया जा सकता है।
+बूलियन परिपथ के लिए सामान्य आधार समुच्चय {AND गेट, OR गेट, NOT गेट} है, जो [[कार्यात्मक पूर्णता]] है, जैसे कि जिससे अन्य सभी बूलियन कार्यों का निर्माण किया जा सकता है।
 == कम्प्यूटेशनल जटिलता ==
-=== पृष्ठभूमि ===
+=== परिप्रेक्ष्य ===
-एक विशेष परिपथ निश्चित आकार के इनपुट पर ही कार्य करता है। यद्यपि, औपचारिक भाषाएँ ([[स्ट्रिंग (कंप्यूटर विज्ञान)]] | [[निर्णय समस्या]]ओं के स्ट्रिंग-आधारित प्रतिनिधित्व) में विभिन्न लंबाई के तार होते हैं, इसलिए भाषाओं को परिपथ द्वारा पूरी तरह से कैप्चर नहीं किया जा सकता है (ट्यूरिंग मशीन मॉडल के विपरीत, जिसमें भाषा है पूरी तरह से ट्यूरिंग मशीन द्वारा वर्णित)। के अतिरिक्त परिपथ परिवार द्वारा भाषा का प्रतिनिधित्व किया जाता है। परिपथ परिवार परिपथ की अनंत सूची है <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}}
+एक विशेष परिपथ निश्चित आकार के इनपुट पर ही कार्य करता है। यद्यपि, औपचारिक भाषाएँ ([[स्ट्रिंग (कंप्यूटर विज्ञान)]] | [[निर्णय समस्या]]ओं के स्ट्रिंग-आधारित प्रतिनिधित्व) में विभिन्न लंबाई के तार होते हैं, इसलिए भाषाओं को परिपथ द्वारा पूरी तरह से कैप्चर नहीं किया जा सकता है (ट्यूरिंग मशीन मॉडल के विपरीत, जिसमें भाषा है पूरी तरह से ट्यूरिंग मशीन द्वारा वर्णित)। के अतिरिक्त परिपथ वर्ग द्वारा भाषा का प्रतिनिधित्व किया जाता है। परिपथ वर्ग परिपथ की अनंत सूची है <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 22: / Line 22: @@
 {{See also|सर्किट जटिलता}}
-कई महत्वपूर्ण कम्प्यूटेशनल जटिलता सिद्धांत को बूलियन परिपथ पर परिभाषित किया जा सकता है, जिसमें परिपथ की गहराई, परिपथ का आकार और एंड गेट्स और और गेट्स के बीच विकल्पों की संख्या सम्मिलित है। उदाहरण के लिए, बूलियन परिपथ की आकार जटिलता परिपथ में फाटकों की संख्या है।
+कई महत्वपूर्ण कम्प्यूटेशनल जटिलता सिद्धांत को बूलियन परिपथ पर परिभाषित किया जा सकता है, जिसमें परिपथ की गहराई, परिपथ का आकार और AND गेट्स और OR गेट्स के बीच विकल्पों की संख्या सम्मिलित है। उदाहरण के लिए, बूलियन परिपथ की आकार जटिलता परिपथ में फाटकों की संख्या है।
 परिपथ के आकार की जटिलता और समय की जटिलता के बीच स्वाभाविक संबंध है।<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 28: / Line 28: @@
 === जटिलता वर्ग ===
 {{Main article|जटिलता वर्ग या बूलियन सर्किट}}
-बूलियन परिपथ के संदर्भ में कई महत्वपूर्ण जटिलता वर्गों को परिभाषित किया गया है। इनमें से सबसे सामान्य है पी/पॉली, भाषाओं का वह समूह जो बहुपद-आकार के परिपथ परिवारों द्वारा तय किया जा सकता है। यह सीधे इस तथ्य से अनुसरण करता है कि भाषाओं में <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>. पी/पॉली और अन्य जटिलता वर्गों के बीच संबंधों का पूरा विवरण पी/पॉली या पी/पॉली का महत्व|पी/पॉली का महत्व पर उपलब्ध है। पी / पॉली में रोचक विशेषता यह भी है कि इसे बहुपद-समय ट्यूरिंग मशीन द्वारा बहुपद-सीमित [[सलाह (जटिलता)]] के साथ मान्यता प्राप्त भाषाओं के वर्ग के रूप में समान रूप से परिभाषित किया जा सकता है।
+बूलियन परिपथ के संदर्भ में कई महत्वपूर्ण जटिलता वर्गों को परिभाषित किया गया है। इनमें से सबसे सामान्य है P/POLY, भाषाओं का वह समूह जो बहुपद-आकार के परिपथ वर्ग द्वारा तय किया जा सकता है। यह सीधे इस तथ्य को अनुसरण करता है कि भाषाओं में <math>\mathsf{TIME}(t(n))</math> परिपथ जटिलता है <math>O(t^2(n))</math> वह [[पी (जटिलता)|P]]<math>\subseteq</math>P/POLY। दूसरे शब्दों में, नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद समय में गणना की जा सकने वाली किसी भी समस्या की गणना बहुपद-आकार के परिपथ वर्ग द्वारा भी की जा सकती है। आगे यह स्थितिया है कि समावेशन उचित है (अर्थात P<math>\subsetneq</math>P/POLY) क्योंकि ऐसी अनिर्णीत समस्याएं हैं जो P/POLY में हैं। P/POLY में कई गुण हैं जो इसे जटिलता वर्गों के बीच संबंधों के अध्ययन में अत्यधिक उपयोगी बनाते हैं। विशेष रूप से, यह P बनाम NP से संबंधित समस्याओं की जाँच करने में सहायक है। उदाहरण के लिए, यदि NP में कोई ऐसी भाषा है जो P/POLY में नहीं है तो P<math>\neq</math>NP.<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}} P/POLY [[बहुपद पदानुक्रम]] के गुणों की जांच करने में भी सहायता करता है। उदाहरण के लिए, यदि [[एनपी (जटिलता)|NP]]⊆ P/POLY, तो पीएच गिर जाता है <math>\Sigma_2^{\mathsf P}</math>. P/POLY और अन्य जटिलता वर्गों के बीच संबंधों का पूरा विवरण P/POLY या P/POLY का महत्व| P/POLY का महत्व पर उपलब्ध है। P/POLY में रोचक विशेषता यह भी है कि इसे बहुपद-समय ट्यूरिंग मशीन द्वारा बहुपद-सीमित [[सलाह (जटिलता)]] के साथ मान्यता प्राप्त भाषाओं के वर्ग के रूप में समान रूप से परिभाषित किया जा सकता है।
-पी/पॉली के दो उपवर्ग जिनके अपने आप में रोचक गुण हैं, एनसी (जटिलता) और [[एसी (जटिलता)]] हैं। इन वर्गों को न केवल उनके परिपथ आकार के संदर्भ में बल्कि उनकी गहराई के संदर्भ में भी परिभाषित किया गया है। परिपथ की गहराई इनपुट नोड से आउटपुट नोड तक सबसे लंबे [[निर्देशित पथ]] की लंबाई है। वर्ग एनसी भाषाओं का समूह है जिसे परिपथ परिवारों द्वारा हल किया जा सकता है जो न केवल बहुपद-आकार तक ही सीमित हैं बल्कि बहुलगणकीय गहराई तक भी सीमित हैं। क्लास एसी को एनसी के समान परिभाषित किया गया है, चूंकि गेट्स को अनबाउंड फैन-इन (अर्थात एंड और और गेट्स को दो से अधिक बिट्स पर प्रयुक्त किया जा सकता है) की अनुमति है। नेकां महत्वपूर्ण वर्ग है क्योंकि यह पता चला है कि यह उन भाषाओं के वर्ग का प्रतिनिधित्व करता है जिनमें कुशल समांतर एल्गोरिदम हैं।
+P/POLY के दो उपवर्ग जिनके अपने आप में रोचक गुण हैं, NC(जटिलता) और [[एसी (जटिलता)|AC(जटिलता)]] हैं। इन वर्गों को न केवल उनके परिपथ आकार के संदर्भ में बल्कि उनकी गहराई के संदर्भ में भी परिभाषित किया गया है। परिपथ की गहराई इनपुट नोड से आउटपुट नोड तक सबसे लंबे [[निर्देशित पथ]] की लंबाई है। वर्ग एनसी भाषाओं का समूह है जिसे परिपथ वर्ग द्वारा हल किया जा सकता है जो न केवल बहुपद-आकार तक ही सीमित हैं बल्कि बहुलगणकीय गहराई तक भी सीमित हैं। क्लास एसी को एनसी के समान परिभाषित किया गया है, चूंकि गेट्स को अनबाउंडेड फैन-इन (अर्थात AND और OR गेट्स को दो से अधिक बिट्स पर प्रयुक्त किया जा सकता है) की अनुमति है। नेकां महत्वपूर्ण वर्ग है क्योंकि यह पता चला है कि यह उन भाषाओं के वर्ग का प्रतिनिधित्व करता है जिनमें कुशल समांतर एल्गोरिदम हैं।
 === परिपथ मूल्यांकन ===
-[[सर्किट वैल्यू प्रॉब्लम|परिपथ वैल्यू प्रॉब्लम]] - दिए गए इनपुट [[बाइनरी स्ट्रिंग]] पर दिए गए बूलियन परिपथ के आउटपुट की गणना करने की समस्या - [[पी-पूर्ण]] निर्णय समस्या है।<ref name="arorabarak"/>{{rp|119}} इसलिए, इस समस्या को इस अर्थ में स्वाभाविक रूप से अनुक्रमिक माना जाता है कि समस्या को हल करने वाला कोई कुशल, अत्यधिक समानांतर एल्गोरिदम नहीं है।
+[[सर्किट वैल्यू प्रॉब्लम|परिपथ वैल्यू प्रॉब्लम]] - दिए गए इनपुट [[बाइनरी स्ट्रिंग]] पर दिए गए बूलियन परिपथ के आउटपुट की गणना करने की समस्या - [[पी-पूर्ण|P-पूर्ण]] निर्णय समस्या है।<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> रैंडम फ्लिप-फ्लॉप नामक अंतर्निहित यादृच्छिक लॉजिक परिपथ की सैद्धांतिक अवधारणा प्रस्तुत की है, जो सेट को पूरा करती है। यह आसानी से यादृच्छिकता को पैक करता है और नियतात्मक बूलियन लॉजिक परिपथ के साथ इंटर-ऑपरेबल है। चूंकि, बूलियन बीजगणित के समकक्ष बीजगणितीय संरचना और विस्तारित सेट के लिए परिपथ निर्माण और कटौती के संबंधित विधि अभी तक अज्ञात हैं।
+लॉजिक परिपथ सरल लॉजिक ऑपरेशंस, AND,OR और NOT (और उनके संयोजन, जैसे गैर-अनुक्रमिक फ्लिप-फ्लॉप या परिपथ नेटवर्क) का भौतिक प्रतिनिधित्व करते हैं, जो गणितीय संरचना बनाते हैं जिसे [[बूलियन बीजगणित]] के रूप में जाना जाता है। वे इस मायने में पूर्ण हैं कि वे कोई भी नियतात्मक एल्गोरिथम निष्पादित कर सकते हैं। यद्यपि, ऐसा होता है कि यह सब कुछ नहीं है। भौतिक विश्व में हम यादृच्छिकता का भी सामना करते हैं, परिमाणीकरण प्रभावों द्वारा नियंत्रित छोटी प्रणालियों में उल्लेखनीय है, जिसे मात्रा यांत्रिकी के सिद्धांत द्वारा वर्णित किया गया है। लॉजिक परिपथ किसी भी यादृच्छिकता का उत्पादन नहीं कर सकते हैं, और इस अर्थ में वे अपूर्ण लॉजिक समुच्चय बनाते हैं। इसका उपाय तर्क नेटवर्क, या कंप्यूटर, जैसे कि [[संभाव्य ट्यूरिंग मशीन]] में तदर्थ यादृच्छिक बिट जनरेटर को जोड़ने में पाया जाता है। हालिया काम<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> रैंडम फ्लिप-फ्लॉप नामक अंतर्निहित यादृच्छिक लॉजिक परिपथ की सैद्धांतिक अवधारणा प्रस्तुत की है, जो समुच्चय को पूरा करती है। यह आसानी से यादृच्छिकता को पैक करता है और नियतात्मक बूलियन लॉजिक परिपथ के साथ इंटर-ऑपरेबल है। चूंकि, बूलियन बीजगणित के समकक्ष बीजगणितीय संरचना और विस्तारित समुच्चय के लिए परिपथ निर्माण और कटौती के संबंधित विधि अभी तक अज्ञात हैं।
 == यह भी देखें ==

v t e डिजिटल इलेक्ट्रॉनिक्स
घटक	ट्रांजिस्टर प्रतिरोधक प्रारंभ करनेवाला संधारित्र मुद्रित इलेक्ट्रॉनिक्स मुद्रित सर्किट बोर्ड विद्युत सर्किट फ्लिप-फ्लॉप मेमोरी सेल संयुक्त तर्क अनुक्रमिक तर्क तर्क द्वार बूलियन सर्किट एकीकृत सर्किट (आईसी) हाइब्रिड इंटीग्रेटेड सर्किट (एचआईसी) मिश्रित सिग्नल एकीकृत सर्किट तीन आयामी एकीकृत सर्किट (3 डी आईसी) एमिटर-युग्मित तर्क (ईसीएल) इरेज़ेबल प्रोग्रामेबल लॉजिक डिवाइस (EPLD) मैक्रोसेल सरणी प्रोग्राम करने योग्य तर्क सरणी (पीएलए) प्रोग्रामेबल लॉजिक डिवाइस (पीएलडी) प्रोग्राम करने योग्य सरणी तर्क (पाल) जेनेरिक सरणी तर्क (जीएएल) कॉम्प्लेक्स प्रोग्रामेबल लॉजिक डिवाइस (CPLD) फील्ड प्रोग्रामेबल गेट ऐरे (FPGA) फील्ड-प्रोग्रामेबल ऑब्जेक्ट ऐरे (एफपीओए) एप्लिकेशन-विशिष्ट एकीकृत सर्किट (एएसआईसी) टेन्सर प्रोसेसिंग यूनिट (टीपीयू)
लिखित	डिजिटल सिग्नल बूलियन बीजगणित तर्क संश्लेषण कंप्यूटर विज्ञान में तर्क कंप्यूटर आर्किटेक्चर डिजिटल सिग्नल अंकीय संकेत प्रक्रिया सर्किट न्यूनीकरण स्विचिंग सर्किट सिद्धांत गेट समकक्ष
डिजाइन	तर्क संश्लेषण स्थान और मार्ग प्लेसमेंट रूटिंग रजिस्टर-ट्रांसफर लेवल हार्डवेयर विवरण भाषा उच्च स्तरीय संश्लेषण औपचारिक तुल्यता जाँच सिंक्रोनस लॉजिक एसिंक्रोनस लॉजिक परिमित अवस्था मशीन पदानुक्रमित राज्य मशीन
अनुप्रयोग	संगणक धातु सामग्री हार्डवेयर एक्सिलरेशन डिजिटल ऑडियो रेडियो डिजिटल फोटोग्राफी डिजिटल टेलीफोन डिजिटल वीडियो छायांकन टेलीविजन इलेक्ट्रॉनिक साहित्य
डिजाइन मुद्दों	मेटास्टेबिलिटी नाड़ी चलाएं

Anonymous

Search

बूलियन परिपथ: Difference between revisions

Namespaces

More

Page actions

Revision as of 14:14, 24 February 2023

Contents

औपचारिक परिभाषा