बूलियन परिपथ

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

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

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

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

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

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

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

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

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

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

जटिलता उपाय

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

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

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

जटिलता वर्ग

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

बूलियन परिपथ के संदर्भ में कई महत्वपूर्ण जटिलता वर्गों को परिभाषित किया गया है। इनमें से सबसे सामान्य है 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. 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-पूर्ण निर्णय समस्या है। इसलिए, इस समस्या को इस अर्थ में स्वाभाविक रूप से अनुक्रमिक माना जाता है कि समस्या को हल करने वाला कोई कुशल, अत्यधिक समानांतर एल्गोरिदम नहीं है।

पूर्णता

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

यह भी देखें

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

फुटनोट्स

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