सर्किट (कंप्यूटर विज्ञान)

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

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

एक परिपथ एक ट्रिपल है $(M,L,G)$, जहाँ

• $M$ मानो का एक समूह है,
• $L$ गेट लेबल का एक सेट है, जिनमें से प्रत्येक $M^{i}$ से $M$ तक कुछ गैर-नकारात्मक पूर्णांक $i$ (जहां $i$ गेट में इनपुट की संख्या का प्रतिनिधित्व करता है) के लिए एक कार्य है और
• $G$,$L$ से लेबल के साथ एक लेबल वाला ग्राफ निर्देशित चक्रीय ग्राफ है

ग्राफ के शीर्षों को गेट्स कहा जाता है। इन-डिग्री $i$ के प्रत्येक गेट $g$ के लिए, गेट $g$ को $L$ के सभी तत्वों $\ell$ द्वारा लेबल किया जा सकता है यदि और केवल यदि $\ell$ को $M^{i}.$ पर परिभाषित किया गया है।

शब्दावली

इन-डिग्री 0 के गेट्स को इनपुट्स या लीव्स कहा जाता है। आउट-डिग्री 0 के गेट्स को आउटपुट कहा जाता है। यदि ग्राफ$G$ में गेट $g$ से गेट $h$ तक कोई किनारा है तो $h$ को $g$ का चाइल्ड कहा जाता है। हमें लगता है कि ग्राफ के शीर्ष पर एक क्रम है, इसलिए हम गेट के $k$ वें बच्चे के बारे में बात कर सकते हैं जब $k$ गेट के आउट-डिग्री से कम है।

परिपथ का आकार परिपथ के नोड्स की संख्या है। गेट $g$ की गहराई $G$ में आउटपुट गेट तक $g$ से प्रारंभ होने वाले सबसे लंबे पथ की लंबाई है। विशेष रूप से, आउट-डिग्री 0 के द्वार केवल गहराई के द्वार हैं। एक परिपथ की गहराई किसी भी द्वार की अधिकतम गहराई है।

स्तर $i$ गहराई के सभी द्वारों का समुच्चय है $i$ एक समतल परिपथ एक ऐसा परिपथ होता है जिसमें गहराई के द्वार $i$ के किनारे $i+1$ या इनपुट से ही गहराई के द्वार से आते हैं। दूसरे शब्दों में, किनारे केवल परिपथ के आसन्न स्तरों के बीच उपस्थित होते हैं। समतल परिपथ की चौड़ाई किसी भी स्तर का अधिकतम आकार है।

मूल्यांकन

इन-डिग्री $i$ और लेबल $l$ वाले गेट $g$ का स्पष्ट मान $V(g)$ सभी गेट $g$ के लिए पुनरावर्ती रूप से परिभाषित किया गया है।

$V(g)={\begin{cases}l&{\text{if }}g{\text{ is an input}}\\l(V(g_{1}),\dotsc ,V(g_{i}))&{\text{otherwise,}}\end{cases}}$

जहां प्रत्येक $g_{j}$ ,$g$ का अभिभावक है

परिपथ का मान प्रत्येक आउटपुट गेट का मान है।

कार्य के रूप में परिपथ

पत्तियों के लेबल वेरिएबल्स भी हो सकते हैं जो $M$ में मान लेते हैं। यदि $n$ पत्तियां हैं, तो परिपथ को $M^{n}$ से $M$ तक एक कार्य के रूप में देखा जा सकता है। फिर परिपथ के एक वर्ग पर विचार करना सामान्य है $(C_{n})_{n\in \mathbb {N} }$, पूर्णांकों द्वारा अनुक्रमित परिपथ का एक क्रम जहां परिपथ $C_{n}$ में $n$ चर होते हैं। परिपथ के वर्गों को इस प्रकार $M^{*}$ से $M$ तक के कार्यों के रूप में देखा जा सकता है।

आकार, गहराई और चौड़ाई की धारणाओं को स्वाभाविक रूप से कार्यों के वर्गों तक बढ़ाया जा सकता है, जो $\mathbb {N}$ से $\mathbb {N}$ तक के कार्य बन जाते हैं; उदाहरण के लिए, $size(n)$ वर्ग के nवें परिपथ का आकार है।

जटिलता और एल्गोरिथम समस्याएं

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

परिपथ जटिलता बूलियन कार्यों को उन परिपथ के आकार या गहराई के संबंध में वर्गीकृत करने का प्रयास करती है जो उनकी गणना कर सकते हैं।

यह भी देखें

• अंकगणितीय परिपथ जटिलता
• बूलियन परिपथ
• परिपथ जटिलता
• प्राकृतिक संख्याओं के सेट पर परिपथ
• जटिलता वर्ग नेकां (जटिलता), एसी (जटिलता) और टीसी (जटिलता)
• यह कितना घूमता है? और बीक्यूपी

संदर्भ

• Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 978-3-540-64310-4.
• Yang, Ke (2001). "Integer Circuit Evaluation Is PSPACE-Complete". Journal of Computer and System Sciences. 63 (2, September 2001): 288–303. doi:10.1006/jcss.2001.1768. ISSN 0022-0000.