एनसी (सम्मिश्रता)

Unsolved problem in computer science:

${\mathsf {NC}}{\overset {?}{=}}{\mathsf {P}}$

(more unsolved problems in computer science)

कम्प्यूटेशनल जटिलता सिद्धांत में, कक्षा एनसी ("निक की कक्षा" के लिए) प्रोसेसर की बहुपद संख्या वाले समानांतर कंप्यूटर पर बहुलगणकीय समय में निर्णय लेने योग्य निर्णय समस्याओं का सेट है। दूसरे शब्दों में, इनपुट आकार एन के साथ एक समस्या एनसी में है यदि स्थिरांक सी और के उपस्थित हैं जैसे कि इसे O((log n)^c) समांतर प्रोसेसर का उपयोग करके समय O(n^k) में समाधान किया जा सकता है। स्टीफन कुक ने निक पिपेंजर के नाम पर "निक क्लास" नाम गढ़ा, जिन्होंने पॉलीलॉगरिदमिक गहराई और बहुपद आकार वाले सर्किट पर व्यापक शोध किया था।

जिस प्रकार क्लास पी (जटिलता) को ट्रैक्टेबल प्रॉब्लम्स (कोभम की थीसिस) के रूप में सोचा जा सकता है, उसी प्रकार एनसी को उन समस्याओं के रूप में सोचा जा सकता है जिसे समानांतर कंप्यूटर पर कुशलता से समाधान किया जा सकता है। NC, P का एक उपसमुच्चय है क्योंकि बहुलगणक समांतर संगणनाओं को बहुपद-समय अनुक्रमिक द्वारा सिम्युलेट किया जा सकता है। यह अज्ञात है कि क्या एनसी = पी, लेकिन अधिकांश शोधकर्ताओं को संदेह है कि यह झूठा है, जिसका अर्थ है कि संभवतः कुछ ट्रैक्टेबल समस्याएं हैं जो "स्वाभाविक रूप से अनुक्रमिक" हैं और समांतरता का उपयोग करके महत्वपूर्ण रूप से तेज नहीं हो सकती हैं। जिस प्रकार एन पी-पूर्ण वर्ग को "संभवतः अट्रैक्टिव" माना जा सकता है, उसी प्रकार एनसी रिडक्शन का उपयोग करते समय क्लास एन पी-सम्पूर्ण को "संभवतः समानांतर नहीं" या"संभवतः स्वाभाविक रूप से अनुक्रमिक" के रूप में सोचा जा सकता है।

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

समतुल्य रूप से, NC को एक ऐसे निर्णय समस्याओं के रूप में परिभाषित किया जा सकता है जिन्हें एक समानरूपी बूलियन सर्किट (जिसे NC के लिए हम संभावनात्मक रूप से लंबाई n में बूलीय सर्किट को n के लॉगारिद्मिक स्थान में हम संगणक सकते हैं) से समाधान किया जा सकता है, जिनमें बहुलघुगणक गहराई और 2 के अधिकतम फैन-इन वाले पॉलिनोमियल गेट के संख्या का प्रयोग किया जाता है।

आरएनसी यादृच्छिकता तक पहुंच के साथ एनसी का विस्तार करने वाला एक वर्ग है।

एनसी में समस्याएं

P के प्रकार, भाषा के एक सामान्य उपयोग के द्वारा, फ़ंक्शन समस्याएं और अविष्कार समस्याएं NC में श्रेणीबद्ध की जा सकती हैं। NC में कई समस्याएं सम्मलित होती हैं, जिनमें निम्नलिखित समस्याएं सम्मलित हैं:

• पूर्णांक जोड़, गुणा और भाग;
• मैट्रिक्स गुणा, निर्धारक, मैट्रिक्स उलटा, श्रेणी;
• बहुपद जीसीडी, सिल्वेस्टर मैट्रिक्स का उपयोग करके रैखिक बीजगणित में कमी करके
• अधिकतम मिलान ढूँढना।

सामान्यतः, इन समस्याओं के लिए अल्गोरिदम अलग-अलग रूप से विकसित करने की आवश्यकता होती है और उन्हें साधारित अल्गोरिदम से सीधे अनुकूलित नहीं किया जा सकता है - गौसियन उपेक्षण और यूक्लिडियन एल्गोरिथ्म में क्रियाएं परिभाषित करते हैं। एक कैरी-लुकहेड योजक के साथ लहर वाहक योजक के विपरीत हो सकता है।

उदाहरण

NC¹ में एक समस्या का उदाहरण एक बिट स्ट्रिंग पर पैरिटी चेक है इस समस्या का स्थितियों एक बिट स्ट्रिंग में 1 की संख्या की गणना करने में होता है जो 1 और 0 से बनी होती है। एक सरल समाधान में, सभी स्ट्रिंग के बिट्स को जोड़कर उपयोग किया जा सकता है। क्योंकि जोड़ना संघटक है$x_{1}+\cdots +x_{n}=(x_{1}+\cdots +x_{\frac {n}{2}})+(x_{{\frac {n}{2}}+1}+\cdots +x_{n})$ इस प्रकार की संपत्ति को पुनरावर्ती रूप से लागू करने से लंबाई का एक बाइनरी ट्री बनाना संभव है$O(log(n))$जिसमें प्रत्येक योग दो बिट के बीच होता है $x_{i}$ और $x_{j}$ बुनियादी तार्किक ऑपरेटरों के माध्यम से व्यक्त किया जा सकता है, उदा। बूलियन अभिव्यक्ति के माध्यम से$(x_{i}\land \neg x_{j})\lor (\neg x_{i}\land x_{j})$.

एनसी पदानुक्रम

NCⁱ एक वर्ग है जो निर्णय समस्याएं सम्मलित करता है जिन्हें एक समानरूपी बूलीय सर्किट के द्वारा पॉलिनोमियल संख्या के गेट्स के साथ समाधान किया जा सकता है जिनमें अधिकतम दो इनपुट होते हैं और गहराई O((log n)ⁱ), होती है, या विनिर्णय समस्याओं का एक वर्ग है जिन्हें समय O((log n)ⁱ) में पॉलिनोमियल संख्या के प्रोसेसर्स के साथ पैरलेल कंप्यूटर पर समाधान किया जा सकता है। स्पष्ट है कि हमारे पास निम्नलिखित होता है।

${\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots \subseteq {\mathsf {NC}}^{i}\subseteq \cdots {\mathsf {NC}}$

जो एनसी-पदानुक्रम बनाता है।

हम एनसी कक्षाओं को अंतरिक्ष कक्षाओं एल (जटिलता) और एनएल (जटिलता) और एसी (जटिलता) से संबंधित कर सकते हैं।

${\mathsf {NC}}^{1}\subseteq {\mathsf {L}}\subseteq {\mathsf {NL}}\subseteq {\mathsf {AC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq {\mathsf {P}}.$

एनसी कक्षाएं एसी कक्षाओं से संबंधित हैं, जिन्हें समान रूप से परिभाषित किया गया है, लेकिन फाटकों में असीमित फैन-इन हैं। प्रत्येक i के लिए, हमारे पास है

${\mathsf {NC}}^{i}\subseteq {\mathsf {AC}}^{i}\subseteq {\mathsf {NC}}^{i+1}.$

इसके तत्काल परिणाम के रूप में, हमारे पास वह NC = AC है।यह ज्ञात है कि दोनों समावेशन i = 0 के लिए सख्त हैं।

इसी प्रकार, हमारे पास NC का एक समकक्ष भी होता है जो हर चरण पर अधिकतम दो वैकल्पिक ट्यूरिंग मशीन पर समाधान किए जाने योग्य समस्याएं है, जहां O(log n) स्थान और $(\log n)^{O(1)}$ विकल्पों के साथ होती हैं।

खुली समस्या: क्या नेकां उचित है?

जटिलता की सिद्धांत में एक महत्वपूर्ण खुला प्रश्न यह है कि क्या हर NC हायरार्की में हर समावेश सही है या नहीं। पापादिमित्रियो ने यह देखा कि, यदि किसी i के लिए NCⁱ = NCⁱ⁺¹ है, तो NCⁱ = NC^j सभी j ≥ i के लिए होता है, और इस परिणाम के अनुसार, NCⁱ = NC होता है। इस अवलोकन को NC-हायरार्की का ध्वंश कहा जाता है क्योंकि यहां समावेशों की श्रृंखला में एक ही समानता भी हो सकती है।

${\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots$

तात्पर्य यह है कि संपूर्ण NC पदानुक्रम कुछ स्तर तक "ढह" जाता है i। इस प्रकार, 2 संभावनाएं हैं

1. ${\mathsf {NC}}^{1}\subset \cdots \subset {\mathsf {NC}}^{i}\subset \cdots \subset {\mathsf {NC}}^{i+j}\subset \cdots {\mathsf {NC}}$
2. ${\mathsf {NC}}^{1}\subset \cdots \subset {\mathsf {NC}}^{i}=\cdots ={\mathsf {NC}}^{i+j}=\cdots {\mathsf {NC}}$

यह व्यापक रूप से माना जाता है कि (1) मामला है, चूंकि अभी तक किसी भी कथन की सच्चाई का कोई प्रमाण नहीं मिला है।

NC⁰

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

बैरिंगटन का प्रमेय

चौड़ाई k और लंबाई m के n वेरिएबल्स के साथ एक ब्रांचिंग प्रोग्राम में m निर्देशों का एक क्रम होता है। प्रत्येक निर्देश एक टपल है (i, p, q) जहां i जांचने के लिए वेरिएबल का इंडेक्स है (1 ≤ i ≤ n), और p और q {1, 2, ..., k} से {1, 2, ..., k तक के फंक्शन हैं }. नंबर 1, 2, ..., k को ब्रांचिंग प्रोग्राम की अवस्थाएं कहा जाता है। कार्यक्रम प्रारंभ में स्थिति 1 में प्रारंभ होता है, और प्रत्येक निर्देश (i, p, q) राज्य को x से p(x') में बदल देता है। ') या q(x), इस बात पर निर्भर करता है कि i वां चर 0 या 1 है। प्रोग्राम की अंतिम स्थिति में इनपुट को मैप करने वाले फ़ंक्शन को यील्ड' कहा जाता है कार्यक्रम का (अधिक सटीक रूप से, एक इनपुट पर उपज किसी भी प्रारंभिक अवस्था को संबंधित अंतिम स्थिति में मैप करने वाला फ़ंक्शन है)। कार्यक्रम स्वीकार करता है एक सेट $A\subset 2^{n}$ चर मूल्यों का जब कार्यों का कुछ सेट होता है $F\subset k^{k}$ जैसे कि एक चर अनुक्रम A में है जब इसकी यील्ड F $x\in 2^{n}$में है।

शाखाओं में बंटने वाले कार्यक्रमों के एक परिवार में प्रत्येक n के लिए n चर के साथ एक शाखाकरण कार्यक्रम होता है। यह एक भाषा को तब स्वीकार करता है जब n वेरिएबल प्रोग्राम लंबाई n इनपुट तक सीमित भाषा को स्वीकार करता है।

यह दिखाना आसान है कि {0,1} पर प्रत्येक भाषा एल को चौड़ाई 5 और घातीय लंबाई के शाखा कार्यक्रमों के परिवार या घातीय चौड़ाई और रैखिक लंबाई के परिवार द्वारा पहचाना जा सकता है।

{0,1} पर प्रत्येक नियमित भाषा को निरंतर चौड़ाई और निर्देशों की रैखिक संख्या के ब्रांचिंग प्रोग्राम के परिवार द्वारा पहचाना जा सकता है (चूंकि DFA को ब्रांचिंग प्रोग्राम में बदला जा सकता है)। BWBP सीमित चौड़ाई और बहुपद लंबाई के शाखा कार्यक्रमों के एक परिवार द्वारा पहचानी जाने वाली भाषाओं के वर्ग को दर्शाता है।

बैरिंगटन की प्रमेय कहता है कि BWBP बिल्कुल एकरूपता (सर्किट) NC¹ है। प्रमाण सममित समूह S₅के समाधान करने योग्य समूह का उपयोग करता है।

प्रमेय बल्कि आश्चर्यजनक है। उदाहरण के लिए, इसका तात्पर्य है कि बहुसंख्यक कार्य की गणना निरंतर चौड़ाई और बहुपद आकार के शाखा कार्यक्रमों के एक परिवार द्वारा की जा सकती है, चूंकि अंतर्ज्ञान यह सुझाव दे सकता है कि बहुपद आकार प्राप्त करने के लिए स्थितियों की एक रैखिक संख्या की आवश्यकता होती है।

बैरिंगटन के प्रमेय का प्रमाण

निरंतर चौड़ाई और बहुपद आकार के एक शाखा कार्यक्रम को NC¹में एक सर्किट में आसानी से परिवर्तित किया जा सकता है (विभाजन और जीत के माध्यम से)।

विपरीत रूप से, सोचें कि हमें NC¹ में एक सर्किट दिया गया है। उपाय की हानि के बिना, मान लें कि यह केवल AND और NOT गेट का ही उपयोग करता है।

लेम्मा 1 — यदि कोई ब्रांचिंग प्रोग्राम उपस्थित है जो कभी-कभी क्रमचय P के रूप में और कभी-कभी क्रमचय Q के रूप में कार्य करता है, पहले निर्देश में α द्वारा क्रमचय को सही-गुणा करके, और अंतिम में निर्देश बाएं- β से गुणा करके, हम समान लंबाई का एक सर्किट बना सकते हैं जो βPα या β} के रूप में व्यवहार करता है Qα, क्रमशः।

एक ब्रांचिंग प्रोग्राम α-कंप्यूटिंग सर्किट सी को कॉल करें यदि यह पहचान के रूप में काम करता है C का आउटपुट 0 है, और as α कब C का आउटपुट 1 है।

लेम्मा 1 के परिणामस्वरूप और तथ्य यह है कि लंबाई 5 के सभी चक्र संयुग्मन वर्ग हैं। इसलिए, किसी भी दो 5-चक्रों के लिए α, β, यदि एक सर्किट C का ब्रांचिंग प्रोग्राम α-कंप्यूटिंग उपस्थित है, तो समान लंबाई का एक ब्रांचिंग प्रोग्राम β-कंप्यूटिंग सर्किट C उपस्थित है।

लेम्मा 2 — 5-चक्र उपस्थित हैं γ, δ जैसे कि उनका कम्यूटेटर ε=γδγ⁻¹ δ⁻¹ एक 5-चक्र है। उदाहरण के लिए, γ = (1 2 3 4 5), δ = (1 3 5 4 2) देने पर ε = (1 3 2 5 4) .

Proof

अब हम बैरिंगटन के प्रमेय को प्रेरण द्वारा सिद्ध करेंगे:

मान लीजिए कि हमारे पास एक सर्किट C है जो इनपुट लेता है x₁,...,x_n और मान लें कि C के सभी उपपरिपथों D और 5-चक्रों α के लिए, एक ब्रांचिंग प्रोग्राम α-कंप्यूटिंग D उपस्थित है। हम दिखाएंगे कि सभी 5-चक्र α के लिए, एक ब्रांचिंग प्रोग्राम α-कंप्यूटिंग C उपस्थित है।

• यदि सर्किट C बस कुछ इनपुट बिट x_i को आउटपुट करता है, तो हमें जिस ब्रांचिंग प्रोग्राम की आवश्यकता है, उसमें केवल एक निर्देश है: चेक करना x_{i</ उप>} का मान (0 या 1), और पहचान को आउटपुट करना या α (क्रमशः)।
• यदि सर्किट C कुछ भिन्न सर्किट A के लिए ¬A आउटपुट करता है, तो एक ब्रांचिंग प्रोग्राम बनाएं α⁻¹-कंप्यूटिंग A और उसके बाद प्रोग्राम के आउटपुट को α से गुणा करें। लेम्मा 1 द्वारा, हमें पहचान या α, यानी α-कंप्यूटिंग ¬A=C को आउटपुट करने के लिए A के लिए एक ब्रांचिंग प्रोग्राम मिलता है।
• यदि परिपथ C परिपथ A और B के लिए A∧B निर्गत करता है, तो γ-'ए' की गणना करें, δ-'बी' की गणना करें, γ⁻¹-'ए' की गणना करें, और δ⁻¹-5-चक्रों γ और δ के विकल्प के लिए B की गणना करें जैसे कि उनका कम्यूटेटर ε=γδγ⁻¹ δ⁻¹ भी 5-चक्र है। (ऐसे तत्वों का अस्तित्व लेम्मा 2 में स्थापित किया गया था।) यदि एक या दोनों सर्किट 0 आउटपुट करते हैं, तो परिणामी प्रोग्राम रद्दीकरण के कारण पहचान होगा; यदि दोनों सर्किट आउटपुट 1 हैं, तो परिणामी प्रोग्राम कम्यूटेटर ε को आउटपुट करेगा। दूसरे शब्दों में, हमें ε-कंप्यूटिंग A∧B प्रोग्राम मिलता है। क्योंकि ε और α दो 5-चक्र हैं, वे संयुग्मित हैं, और इसलिए एक प्रोग्राम उपस्थित है α-कंप्यूटिंग A ∧B लेम्मा 1 द्वारा।

यह मानकर कि उपपरिपथों में शाखाओं में बंटे कार्यक्रम हैं ताकि वे α- सभी 5-चक्रों के लिए संगणना कर सकें α∈S₅ , हमने दिखाया है कि आवश्यकता के अनुसार C में भी यह गुण है।

ब्रांचिंग प्रोग्राम का आकार अधिकतम 4^d है, जहाँ d सर्किट की गहराई है। यदि सर्किट में लॉगरिदमिक गहराई है, तो ब्रांचिंग प्रोग्राम में बहुपद लंबाई है।

संदर्भ

• Arora, Sanjeev; Barak, Boaz (2009). Computational complexity. A modern approach. Cambridge University Press. ISBN 978-0-521-42426-4. Zbl 1193.68112.
• Clote, Peter; Kranakis, Evangelos (2002). Boolean functions and computation models. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. ISBN 3-540-59436-1. Zbl 1016.94046.
• Greenlaw, Raymond, James Hoover, and Walter Ruzzo. Limits To Parallel computation; P-Completeness Theory. ISBN 0-19-508591-4
• Kozen, Dexter C. (1992). The design and analysis of algorithms. Lectures 28 - 34 and 36
• Kozen, Dexter C. (2006). Theory of Computation. Texts in Computer Science. Springer-Verlag. ISBN 1-84628-297-7. Zbl 1102.68025. Lecture 12: Relation of NC to Time-Space Classes
• Papadimitriou, Christos (1993). "Section 15.3: The class NC". Computational Complexity (1st ed.). Addison Wesley. pp. 375–381. ISBN 0-201-53082-1.
• Straubing, Howard (1994). Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Basel: Birkhäuser. ISBN 3-7643-3719-2. Zbl 0816.68086.
• Vollmer, Heribert (1998). Introduction to circuit complexity. A uniform approach. Texts in Theoretical Computer Science. Berlin: Springer-Verlag. ISBN 3-540-64310-9. Zbl 0931.68055.