बूलियन परिपथ

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

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

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

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

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

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

बूलियन परिपथ के लिए सामान्य आधार सेट {एंड गेट, और गेट, नॉट गेट} है, जो कार्यात्मक पूर्णता है, i। इ। जिससे अन्य सभी बूलियन कार्यों का निर्माण किया जा सकता है।

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

पृष्ठभूमि

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

जटिलता उपाय

See also: सर्किट जटिलता

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

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

जटिलता वर्ग

Main article: जटिलता वर्ग या बूलियन सर्किट

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

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

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

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

पूर्णता

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

यह भी देखें

• परिपथ संतुष्टि
• लॉजिक गेट
• बूलियन तर्क
• स्विचिंग लेम्मा

फुटनोट्स

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