बूलियन परिपथ और परिपथ जटिलता

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

Definition

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

Scope

यह विषय बूलियन परिपथ और सूत्रों, जटिलता के आकार और गहराई के मापों, एकसमान बनाम गैर-एकरूप मॉडल, NC और AC जैसे निम्न-गहराई वाले वर्गों, परिपथ निम्न सीमाओं और जटिलता वर्गों के पृथक्करण के बीच संबंध, और प्रतिबंधित परिपथ परिवारों के लिए ऐतिहासिक निम्न-सीमा परिणामों को शामिल करता है।

Core questions

• संगणना का गेट-नेटवर्क दृष्टिकोण अनुक्रमिक मशीनों से कैसे भिन्न है?
• परिपथ का आकार और गहराई क्या मापते हैं, और वे समय और समानांतरता से कैसे संबंधित हैं?
• परिपथ निम्न सीमाएं जटिलता वर्गों को अलग करने का एक मार्ग क्यों हैं?
• कौन सी निम्न सीमाएं ज्ञात हैं, और कौन सी बाधाएं मजबूत सीमाओं को रोकती हैं?

Key theories

गैर-एकरूपता और वर्ग P/poly

परिपथ प्रत्येक इनपुट लंबाई के लिए एक अलग मशीन की अनुमति देते हैं, जिससे गैर-एकरूप वर्ग P/poly बनता है जिसमें P शामिल है; यह दिखाना कि एक NP-पूर्ण समस्या में बहुपद-आकार के परिपथों की कमी है, P को NP से अलग करेगा, जो परिपथ निम्न सीमाओं को प्रेरित करता है।

प्रतिबंधित परिपथों के लिए निम्न सीमाएं

सीमित परिवारों के लिए मजबूत निम्न सीमाएं ज्ञात हैं, जैसे कि समानता की गणना करने वाले निरंतर-गहराई वाले परिपथों के लिए आवश्यक घातीय आकार, भले ही सामान्य परिपथों के लिए निम्न सीमाएं पहुंच से बाहर बनी हुई हैं।

Clinical relevance

परिपथ डिजिटल हार्डवेयर का प्राकृतिक मॉडल हैं, इसलिए परिपथ जटिलता चिप डिजाइन और समानांतर संगणना की सीमाओं को सूचित करती है; निम्न-गहराई वाले वर्ग यह दर्शाते हैं कि कई प्रोसेसर के साथ कितनी तेजी से गणना की जा सकती है, और परिपथ निम्न सीमाएं P बनाम NP जैसे प्रश्नों को हल करने के दीर्घकालिक प्रयास में एक प्रमुख रणनीति हैं।

History

शैनन ने 1937 में बूलियन बीजगणित को स्विचिंग परिपथों से जोड़ा, और परिपथ जटिलता 1980 के दशक में एक अनुशासन के रूप में परिपक्व हुई जब फर्स्ट, सैक्स, सिप्सेर और अन्य ने समानता के लिए निरंतर-गहराई वाली निम्न सीमाओं को साबित किया, और रज़बोरोव और स्मोलेंस्की ने बीजगणितीय विधियों को विकसित किया, इससे पहले कि प्राकृतिक-प्रमाण बाधा ने यह खुलासा किया कि सामान्य निम्न सीमाएं इतनी मायावी क्यों हैं।

Key figures

• Claude Shannon
• Alexander Razborov
• Andrew Yao
• Roman Smolensky

Seminal works

• aroraBarak2009
• vollmer1999

Frequently asked questions

परिपथ ट्यूरिंग मशीनों से कैसे भिन्न हैं?

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

शोधकर्ता परिपथ निम्न सीमाओं के बारे में क्यों परवाह करते हैं?

यह साबित करना कि NP में एक समस्या के लिए बहुत बड़े परिपथों की आवश्यकता होती है, जटिलता वर्गों को अलग करेगा और P बनाम NP को हल कर सकता है। प्रतिबंधित परिपथ परिवारों के लिए निम्न सीमाएं ज्ञात हैं, लेकिन उन्हें सामान्य परिपथों तक विस्तारित करना औपचारिक बाधाओं से बाधित है, जिससे यह क्षेत्र की सबसे गहरी खुली चुनौतियों में से एक बन गया है।