एनसी (सम्मिश्रता): Difference between revisions

Revision as of 10:32, 17 May 2023

Unsolved problem in computer science:

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

(more unsolved problems in computer science)

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

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

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

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

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

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

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

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

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

उदाहरण

NC¹ में एक समस्या का उदाहरण एक बिट स्ट्रिंग पर पैरिटी चेक है ^[6] इस समस्या का मामला एक बिट स्ट्रिंग में 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) i)$ , होती है, या विनिर्णय समस्याओं का एक वर्ग है जिन्हें समय O((log n)ⁱ) में पॉलिनोमियल संख्या के प्रोसेसर्स के साथ पैरलेल कंप्यूटर पर समाधान किया जा सकता है। स्पष्ट है कि हमारे पास निम्नलिखित होता है।

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

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

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

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

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

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

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

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

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

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

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

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

${\mathsf {NC}}^{1}\subset \cdots \subset {\mathsf {NC}}^{i}\subset \cdots \subset {\mathsf {NC}}^{i+j}\subset \cdots {\mathsf {NC}}$
${\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}$ जैसे कि एक चर अनुक्रम $x\in 2^{n}$ A में है जब इसकी उपज F में है।

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

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

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

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

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

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

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

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

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

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

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

लेम्मा 2 — 5-चक्र मौजूद हैं γ, δ जैसे कि उनका कम्यूटेटर $ε = γδγ -1 δ -1$ एक 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 की गणना करें जैसे कि उनका कम्यूटेटर $ε = γδγ -1 δ -1$ भी 5-चक्र है। (ऐसे तत्वों का अस्तित्व लेम्मा 2 में स्थापित किया गया था।) यदि एक या दोनों सर्किट 0 आउटपुट करते हैं, तो परिणामी प्रोग्राम रद्दीकरण के कारण पहचान होगा; यदि दोनों सर्किट आउटपुट 1 हैं, तो परिणामी प्रोग्राम कम्यूटेटर ε को आउटपुट करेगा। दूसरे शब्दों में, हमें ε-कंप्यूटिंग A∧B प्रोग्राम मिलता है। क्योंकि ε और α दो 5-चक्र हैं, वे संयुग्मित हैं, और इसलिए एक प्रोग्राम मौजूद है α-कंप्यूटिंग A ∧B लेम्मा 1 द्वारा।

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

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

↑ "Towards a complexity theory of synchronous parallel computation. D L'Enseignement mathematique 27" (in English). {{cite journal}}: Cite journal requires |journal= (help)
↑ Cook, Stephen A. (1985-01-01). "तेजी से समांतर एल्गोरिदम के साथ समस्याओं का वर्गीकरण". Information and Control. International Conference on Foundations of Computation Theory (in English). 64 (1): 2–22. doi:10.1016/S0019-9958(85)80041-3. ISSN 0019-9958.
↑ Pippenger, Nicholas (1979). "एक साथ संसाधन सीमा पर". 20th Annual Symposium on Foundations of Computer Science (SFCS 1979) (in English): 307–311. doi:10.1109/SFCS.1979.29. ISSN 0272-5428. S2CID 7029313.
↑ Arora & Barak (2009) p.120
↑ ^5.0 ^5.1 ^5.2 Arora & Barak (2009) p.118
↑ David Mix Barrington; Alexis Maciel (2000-07-18). "Lecture 2: The Complexity of Some Problems" (PDF). IAS/PCMI Summer Session 2000 - Clay Mathematics Undergraduate Program - Basic Course on Computational Complexity. Clarkson University. Retrieved 2021-11-11.
↑ Papadimitriou (1994) Theorem 16.1
↑ ^8.0 ^8.1 Clote & Kranakis (2002) p.437
↑ Clote & Kranakis (2002) p.12
↑ S. Bellantoni and I. Oitavem (2004). "डेल्टा अक्ष के साथ नेकां को अलग करना". Theoretical Computer Science. 318 (1–2): 57–78. doi:10.1016/j.tcs.2003.10.021.
↑ ^11.0 ^11.1 Clote & Kranakis (2002) p.50
↑ Barrington, David A. (1989). "Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹" (PDF). J. Comput. Syst. Sci. 38 (1): 150–164. doi:10.1016/0022-0000(89)90037-8. ISSN 0022-0000. Zbl 0667.68059.

संदर्भ

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.

[1] "Towards a complexity theory of synchronous parallel computation. D L'Enseignement mathematique 27" (in English). {{cite journal}}: Cite journal requires |journal= (help)

[2] Cook, Stephen A. (1985-01-01). "तेजी से समांतर एल्गोरिदम के साथ समस्याओं का वर्गीकरण". Information and Control. International Conference on Foundations of Computation Theory (in English). 64 (1): 2–22. doi:10.1016/S0019-9958(85)80041-3. ISSN 0019-9958.

[3] Pippenger, Nicholas (1979). "एक साथ संसाधन सीमा पर". 20th Annual Symposium on Foundations of Computer Science (SFCS 1979) (in English): 307–311. doi:10.1109/SFCS.1979.29. ISSN 0272-5428. S2CID 7029313.

[AB120-4] Arora & Barak (2009) p.120

[AB118-5] 5.0 ^5.1 ^5.2 Arora & Barak (2009) p.118

[6] David Mix Barrington; Alexis Maciel (2000-07-18). "Lecture 2: The Complexity of Some Problems" (PDF). IAS/PCMI Summer Session 2000 - Clay Mathematics Undergraduate Program - Basic Course on Computational Complexity. Clarkson University. Retrieved 2021-11-11.

[7] Papadimitriou (1994) Theorem 16.1

[CK437-8] 8.0 ^8.1 Clote & Kranakis (2002) p.437

[CK12-9] Clote & Kranakis (2002) p.12

[10] S. Bellantoni and I. Oitavem (2004). "डेल्टा अक्ष के साथ नेकां को अलग करना". Theoretical Computer Science. 318 (1–2): 57–78. doi:10.1016/j.tcs.2003.10.021.

[CK50-11] 11.0 ^11.1 Clote & Kranakis (2002) p.50

[Bar89-12] Barrington, David A. (1989). "Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹" (PDF). J. Comput. Syst. Sci. 38 (1): 150–164. doi:10.1016/0022-0000(89)90037-8. ISSN 0022-0000. Zbl 0667.68059.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

@@ Line 1: / Line 1: @@
 {{unsolved|computer science|{{tmath|1= \mathsf{NC} \overset{?}{=} \mathsf{P} }}}}
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, कक्षा एनसी (निक की कक्षा के लिए) प्रोसेसर की बहुपद संख्या के साथ समांतर कंप्यूटिंग पर पॉलीलॉगरिदमिक समय में निर्णय लेने योग्य [[निर्णय समस्या]]ओं का सेट है। दूसरे शब्दों में, इनपुट आकार ''n'' के साथ एक समस्या NC में है यदि स्थिरांक ''c'' और ''k'' मौजूद हैं जैसे कि इसे समय पर हल किया जा सकता है {{math|''[[Big O notation|O]]''((log ''n'')<sup>''c''</sup>)}} का उपयोग करना {{math|''[[Big O notation|O]]''(''n''<sup>''k''</sup>)}} समानांतर प्रोसेसर। [[स्टीफन कुक]]<ref>{{Cite journal|title=Towards a complexity theory of synchronous parallel computation. D L'Enseignement mathematique 27|url=http://citeseerx.ist.psu.edu/showciting?cid=1672592|language=en}}</ref><ref>{{Cite journal|last=Cook|first=Stephen A.|date=1985-01-01|title=तेजी से समांतर एल्गोरिदम के साथ समस्याओं का वर्गीकरण|journal=Information and Control|series=International Conference on Foundations of Computation Theory|language=en|volume=64|issue=1|pages=2–22|doi=10.1016/S0019-9958(85)80041-3|issn=0019-9958|doi-access=free}}</ref> निक की कक्षा का नाम [[निक पिपेंजर]] के नाम पर रखा गया, जिन्होंने व्यापक शोध किया था<ref>{{Cite journal|last=Pippenger|first=Nicholas|date=1979|title=एक साथ संसाधन सीमा पर|url=https://www.infona.pl//resource/bwmeta1.element.ieee-art-000004568025|journal=20th Annual Symposium on Foundations of Computer Science (SFCS 1979)|language=en|pages=307–311|doi=10.1109/SFCS.1979.29|s2cid=7029313 |issn=0272-5428}}</ref> बहुलगणकीय गहराई और बहुपद आकार वाले परिपथों पर।<ref name=AB120>Arora & Barak (2009) p.120</ref>
+[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, कक्षा एनसी ("निक की कक्षा" के लिए) प्रोसेसर की बहुपद संख्या वाले समानांतर कंप्यूटर पर बहुलगणकीय समय में निर्णय लेने योग्य [[निर्णय समस्या]]ओं का सेट है। दूसरे शब्दों में, इनपुट आकार एन के साथ एक समस्या एनसी में है यदि स्थिरांक सी और के  उपस्थित हैं जैसे कि इसे {{math|''[[Big O notation|O]]''((log ''n'')<sup>''c''</sup>)}} समांतर प्रोसेसर का उपयोग करके समय {{math|''[[Big O notation|O]]''(''n''<sup>''k''</sup>)}} में समाधान किया जा सकता है। [[स्टीफन कुक]]<ref>{{Cite journal|title=Towards a complexity theory of synchronous parallel computation. D L'Enseignement mathematique 27|url=http://citeseerx.ist.psu.edu/showciting?cid=1672592|language=en}}</ref><ref>{{Cite journal|last=Cook|first=Stephen A.|date=1985-01-01|title=तेजी से समांतर एल्गोरिदम के साथ समस्याओं का वर्गीकरण|journal=Information and Control|series=International Conference on Foundations of Computation Theory|language=en|volume=64|issue=1|pages=2–22|doi=10.1016/S0019-9958(85)80041-3|issn=0019-9958|doi-access=free}}</ref> ने [[निक पिपेंजर]] के नाम पर "निक क्लास" नाम गढ़ा, जिन्होंने पॉलीलॉगरिदमिक गहराई और बहुपद आकार वाले सर्किट पर व्यापक शोध <ref>{{Cite journal|last=Pippenger|first=Nicholas|date=1979|title=एक साथ संसाधन सीमा पर|url=https://www.infona.pl//resource/bwmeta1.element.ieee-art-000004568025|journal=20th Annual Symposium on Foundations of Computer Science (SFCS 1979)|language=en|pages=307–311|doi=10.1109/SFCS.1979.29|s2cid=7029313 |issn=0272-5428}}</ref> किया था।<ref name=AB120>Arora & Barak (2009) p.120</ref>
-जिस तरह क्लास [[पी (जटिलता)]] को ट्रैक्टेबल प्रॉब्लम्स (कोभम की थीसिस) के रूप में सोचा जा सकता है, उसी तरह एनसी को उन समस्याओं के रूप में सोचा जा सकता है जिन्हें एक समानांतर कंप्यूटर पर कुशलता से हल किया जा सकता है।<ref name=AB118>Arora & Barak (2009) p.118</ref> NC, P का एक उपसमुच्चय है क्योंकि बहुलगणक समांतर संगणनाओं को बहुपद-समय अनुक्रमिक द्वारा सिम्युलेट किया जा सकता है। यह अज्ञात है कि क्या एनसी = पी, लेकिन अधिकांश शोधकर्ताओं को संदेह है कि यह झूठा है, जिसका अर्थ है कि शायद कुछ ट्रैक्टेबल समस्याएं हैं जो स्वाभाविक रूप से अनुक्रमिक हैं और समांतरता का उपयोग करके महत्वपूर्ण रूप से तेज नहीं हो सकती हैं। जिस तरह एन[[पी-पूर्ण]] वर्ग को शायद अट्रैक्टिव माना जा सकता है, उसी तरह एनसी रिडक्शन का उपयोग करते समय क्लास [[एन पी-सम्पूर्ण]] को शायद समानांतर या शायद स्वाभाविक रूप से अनुक्रमिक नहीं माना जा सकता है।
+जिस  प्रकार क्लास [[पी (जटिलता)]] को ट्रैक्टेबल प्रॉब्लम्स (कोभम की थीसिस) के रूप में सोचा जा सकता है, उसी  प्रकार एनसी को ऐसी प्रॉब्लम के रूप में सोचा जा सकता है जिसे समानांतर कंप्यूटर पर कुशलता से समाधान किया जा सकता है।<ref name="AB118">Arora & Barak (2009) p.118</ref> NC, P का एक उपसमुच्चय है क्योंकि बहुलगणक समांतर संगणनाओं को बहुपद-समय अनुक्रमिक द्वारा सिम्युलेट किया जा सकता है। यह अज्ञात है कि क्या एनसी = पी, लेकिन अधिकांश शोधकर्ताओं को संदेह है कि यह झूठा है,  जिसका अर्थ है कि संभवतः कुछ ट्रैक्टेबल समस्याएं हैं जो "स्वाभाविक रूप से अनुक्रमिक" हैं और समांतरता का उपयोग करके महत्वपूर्ण रूप से तेज नहीं हो सकती हैं। जिस  प्रकार एन [[पी-पूर्ण]] वर्ग को "संभवतः अट्रैक्टिव" माना जा सकता है, उसी  प्रकार एनसी रिडक्शन का उपयोग करते समय क्लास [[एन पी-सम्पूर्ण]] को  "संभवतः समानांतर नहीं" या"संभवतः स्वाभाविक रूप से अनुक्रमिक" के रूप में सोचा जा सकता है।
 परिभाषा में समानांतर कंप्यूटर को ''समानांतर, रैंडम-एक्सेस मशीन'' ([[समानांतर रैंडम एक्सेस मशीन]]) माना जा सकता है। यह एक समानांतर कंप्यूटर है जिसमें मेमोरी का एक केंद्रीय पूल होता है, और कोई भी प्रोसेसर निरंतर समय में किसी भी मेमोरी को एक्सेस कर सकता है। एनसी की परिभाषा इस बात से प्रभावित नहीं होती है कि कैसे PRAM एक से अधिक प्रोसेसर द्वारा एक ही बिट तक एक साथ पहुंच को संभालता है। यह CRCW, CREW, या EREW हो सकता है। उन मॉडलों के विवरण के लिए समानांतर रैंडम एक्सेस मशीन देखें।
-समतुल्य रूप से, एनसी को उन निर्णय समस्याओं के रूप में परिभाषित किया जा सकता है जो एक [[बूलियन सर्किट]] (जो इनपुट की लंबाई से गणना की जा सकती है, एनसी के लिए, हम मानते हैं कि हम लॉगरिदमिक स्पेस में 'एन' आकार के बूलियन सर्किट की गणना कर सकते हैं। 'एन'') [[बहुलघुगणक]] गहराई और 2 के अधिकतम फैन-इन वाले फाटकों की बहुपद संख्या के साथ।
+समकालीन रूप से, NC को एक ऐसे निर्णय समस्याओं के रूप में परिभाषित किया जा सकता है जिन्हें एक समानरूपी [[बूलियन सर्किट]] (जिसे NC के लिए हम संभावनात्मक रूप से लंबाई n में बूलीय सर्किट को n के लॉगारिद्मिक स्थान में हम संगणक सकते हैं) ''से समाधान किया जा सकता है, जिनमें [[बहुलघुगणक]] गहराई और 2 के अधिकतम फैन-इन वाले पॉलिनोमियल गेट के संख्या का प्रयोग किया जाता है।''
 आरएनसी यादृच्छिकता तक पहुंच के साथ एनसी का विस्तार करने वाला एक वर्ग है।
-== एनसी == में समस्याएं
+=== एनसी में समस्याएं ===
-पी के साथ, भाषा के थोड़े से दुरुपयोग से, कोई भी कार्य समस्याओं को वर्गीकृत कर सकता है और एनसी में होने वाली समस्याओं को खोज सकता है। नेकां सहित कई समस्याओं को शामिल करने के लिए जाना जाता है
+P के  प्रकार, भाषा के एक सामान्य उपयोग के द्वारा, फ़ंक्शन समस्याएं और खोज समस्याएं NC में श्रेणीबद्ध की जा सकती हैं। NC में कई समस्याएं  सम्मलित होती हैं, जिनमें निम्नलिखित समस्याएं  सम्मलित हैं:
 * पूर्णांक जोड़, गुणा और भाग;
-* मैट्रिक्स गुणा, निर्धारक, [[मैट्रिक्स उलटा]], रैंक;
+* मैट्रिक्स गुणा, निर्धारक, [[मैट्रिक्स उलटा]], श्रेणी;
 * बहुपद जीसीडी, [[सिल्वेस्टर मैट्रिक्स]] का उपयोग करके रैखिक बीजगणित में कमी करके
-* एक अधिकतम मिलान ढूँढना।
+* अधिकतम मिलान ढूँढना।
-अक्सर उन समस्याओं के लिए एल्गोरिदम को अलग से आविष्कार करना पड़ता था और प्रसिद्ध एल्गोरिदम से भोलेपन से अनुकूलित नहीं किया जा सकता था - [[ गाउस विलोपन ]] और [[यूक्लिडियन एल्गोरिथ्म]] अनुक्रम में किए गए संचालन पर भरोसा करते हैं। एक [[कैरी-लुकहेड योजक]] के साथ [[लहर वाहक योजक]] के विपरीत हो सकता है।
+सामान्यतः, इन समस्याओं के लिए अल्गोरिदम अलग-अलग रूप से विकसित करने की आवश्यकता होती है और उन्हें साधारित अल्गोरिदम से सीधे अनुकूलित नहीं किया जा सकता है - [[ गाउस विलोपन |गौसियन उपेक्षण]] और [[यूक्लिडियन एल्गोरिथ्म]] में क्रियाएं परिभाषित करते हैं। एक [[कैरी-लुकहेड योजक]] के साथ [[लहर वाहक योजक]] के विपरीत हो सकता है।
 === उदाहरण ===
-नेकां में समस्या का एक उदाहरण<sup>1</sup> बिट स्ट्रिंग पर पैरिटी चेक है।<ref>{{cite web|url=https://lin-web.clarkson.edu/~alexis/PCMI/Notes/lectureB02.pdf|title=Lecture 2: The Complexity of Some Problems|date=2000-07-18|author1=David Mix Barrington|author2=Alexis Maciel|work=IAS/PCMI Summer Session 2000 - Clay Mathematics Undergraduate Program - Basic Course on Computational Complexity|publisher=[[Clarkson University]]|accessdate=2021-11-11}}</ref> समस्या 1 और 0 से बनी एक स्ट्रिंग में 1s की संख्या की गणना करने में होती है। एक सरल समाधान में स्ट्रिंग के सभी बिट्स का योग होता है। क्योंकि योग साहचर्य है, <math>x_1 + \cdots + x_n = (x_1 + \cdots + x_{\frac{n}{2}}) + (x_{\frac{n}{2} + 1} + \cdots + x_n)</math>. इस तरह की संपत्ति को पुनरावर्ती रूप से लागू करने से लंबाई का एक [[बाइनरी ट्री]] बनाना संभव है <math>O(log(n))</math> जिसमें प्रत्येक योग दो बिट के बीच होता है <math>x_i</math> और <math>x_j</math> बुनियादी [[तार्किक ऑपरेटर]]ों के माध्यम से अभिव्यक्त किया जा सकता है, उदा। बूलियन अभिव्यक्ति के माध्यम से <math>(x_i \land \neg x_j) \lor (\neg x_i \land x_j)</math>.
+NC<sup>1</sup> में एक समस्या का उदाहरण एक बिट स्ट्रिंग पर पैरिटी चेक है <ref>{{cite web|url=https://lin-web.clarkson.edu/~alexis/PCMI/Notes/lectureB02.pdf|title=Lecture 2: The Complexity of Some Problems|date=2000-07-18|author1=David Mix Barrington|author2=Alexis Maciel|work=IAS/PCMI Summer Session 2000 - Clay Mathematics Undergraduate Program - Basic Course on Computational Complexity|publisher=[[Clarkson University]]|accessdate=2021-11-11}}</ref> इस समस्या का मामला एक बिट स्ट्रिंग में 1 की संख्या की गणना करने में होता है जो 1 और 0 से बनी होती है। एक सरल समाधान में, सभी स्ट्रिंग के बिट्स को जोड़कर उपयोग किया जा सकता है। क्योंकि जोड़ना संघटक है<math>x_1 + \cdots + x_n = (x_1 + \cdots + x_{\frac{n}{2}}) + (x_{\frac{n}{2} + 1} + \cdots + x_n)</math> इस  प्रकार की संपत्ति को पुनरावर्ती रूप से लागू करने से लंबाई का एक [[बाइनरी ट्री]] बनाना संभव है<math>O(log(n))</math>जिसमें प्रत्येक योग दो बिट के बीच होता है <math>x_i</math> और <math>x_j</math> बुनियादी [[तार्किक ऑपरेटर|तार्किक ऑपरेटरों]] के माध्यम से व्यक्त किया जा सकता है, उदा। बूलियन अभिव्यक्ति के माध्यम से<math>(x_i \land \neg x_j) \lor (\neg x_i \land x_j)</math>.
 == एनसी पदानुक्रम ==
-एनसी<sup>i</sup> अधिक से अधिक दो इनपुट और गहराई वाले गेटों की बहुपद संख्या के साथ यूनिफ़ॉर्म बूलियन सर्किट द्वारा तय की जाने वाली निर्णय समस्याओं का वर्ग है {{math|''O''((log ''n'')<sup>''i''</sup>)}}, या समय ओ में हल करने योग्य निर्णय समस्याओं का वर्ग ((लॉग एन)<sup>i</sup>) प्रोसेसर की बहुपद संख्या वाले समानांतर कंप्यूटर पर। स्पष्ट रूप से, हमारे पास है
+'''NC'''<sup>''i''</sup>  एक वर्ग है जो निर्णय समस्याएं  सम्मलित करता है जिन्हें एक समानरूपी बूलीय सर्किट के द्वारा पॉलिनोमियल संख्या के गेट्स के साथ समाधान किया जा सकता है जिनमें अधिकतम दो इनपुट होते हैं और गहराई {{math|''O''((log ''n'')<sup>''i''</sup>)}}, होती है, या विनिर्णय समस्याओं का एक वर्ग है जिन्हें समय ''O''((log ''n'')<sup>''i''</sup>) में पॉलिनोमियल संख्या के प्रोसेसर्स के साथ पैरलेल कंप्यूटर पर समाधान किया जा सकता है। स्पष्ट है कि हमारे पास निम्नलिखित होता है।
 :<math>\mathsf{NC}^1 \subseteq \mathsf{NC}^2 \subseteq \cdots \subseteq \mathsf{NC}^i \subseteq \cdots \mathsf{NC}</math>
 जो एनसी-पदानुक्रम बनाता है।
-हम एनसी कक्षाओं को अंतरिक्ष कक्षाओं [[एल (जटिलता)]] और [[एनएल (जटिलता)]] से संबंधित कर सकते हैं।<ref>Papadimitriou (1994) Theorem 16.1</ref> और [[एसी (जटिलता)]]।<ref name=CK437>Clote & Kranakis (2002) p.437</ref>
+हम एनसी कक्षाओं को अंतरिक्ष कक्षाओं [[एल (जटिलता)]] और [[एनएल (जटिलता)]]<ref>Papadimitriou (1994) Theorem 16.1</ref> और [[एसी (जटिलता)]] से संबंधित कर सकते हैं।<ref name=CK437>Clote & Kranakis (2002) p.437</ref>
 :<math> \mathsf{NC}^1 \subseteq \mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{AC}^1 \subseteq \mathsf{NC}^2 \subseteq \mathsf{P}.</math>
 एनसी कक्षाएं एसी कक्षाओं से संबंधित हैं, जिन्हें समान रूप से परिभाषित किया गया है, लेकिन फाटकों में असीमित फैन-इन हैं। प्रत्येक i के लिए, हमारे पास है<ref name=AB118/><ref name="CK437"/>
 :<math>\mathsf{NC}^i \subseteq \mathsf{AC}^i \subseteq \mathsf{NC}^{i+1}.</math>
-इसके तत्काल परिणाम के रूप में, हमारे पास वह NC = AC है।<ref name=CK12>Clote & Kranakis (2002) p.12</ref>
+इसके तत्काल परिणाम के रूप में, हमारे पास वह NC = AC है।<ref name=CK12>Clote & Kranakis (2002) p.12</ref>यह ज्ञात है कि दोनों समावेशन i = 0 के लिए सख्त हैं।<ref name=AB118/>
-यह ज्ञात है कि दोनों समावेशन i = 0 के लिए सख्त हैं।<ref name=AB118/>
-इसी प्रकार, हमारे पास यह है कि एनसी एक [[वैकल्पिक ट्यूरिंग मशीन]] पर हल करने योग्य समस्याओं के बराबर है जो प्रत्येक चरण में '' ओ '' (लॉग '' एन '') स्थान के साथ अधिकतम दो विकल्पों तक सीमित है और <math>(\log n)^{O(1)}</math> विकल्प।<ref>{{cite journal|author=S. Bellantoni and I. Oitavem|title=डेल्टा अक्ष के साथ नेकां को अलग करना|journal=Theoretical Computer Science|volume=318|issue=1–2|year=2004|pages=57–78|doi=10.1016/j.tcs.2003.10.021|doi-access=free}}</ref>
+इसी  प्रकार, हमारे पास NC का एक समकक्ष भी होता है जो हर चरण पर अधिकतम दो [[वैकल्पिक ट्यूरिंग मशीन]] पर समाधान किए जाने योग्य समस्याएं है, जहां ''O''(log ''n'') स्थान और <math>(\log n)^{O(1)}</math> विकल्पों के साथ होती हैं।<ref>{{cite journal|author=S. Bellantoni and I. Oitavem|title=डेल्टा अक्ष के साथ नेकां को अलग करना|journal=Theoretical Computer Science|volume=318|issue=1–2|year=2004|pages=57–78|doi=10.1016/j.tcs.2003.10.021|doi-access=free}}</ref>
 === खुली समस्या: क्या नेकां उचित है? ===
-कम्प्यूटेशनल जटिलता सिद्धांत में एक प्रमुख खुला प्रश्न यह है कि एनसी पदानुक्रम में प्रत्येक नियंत्रण उचित है या नहीं। यह Papadimitriou द्वारा देखा गया कि, यदि NC<sup>मैं</sup> = 'एनसी'<sup>i+1</sup> कुछ i के लिए, फिर 'NC'<sup>मैं</sup> = 'एनसी'<sup>j</sup> सभी j ≥ i के लिए, और परिणामस्वरूप, 'NC'<sup>मैं</sup> = 'एनसी'। इस अवलोकन को 'एनसी'-पदानुक्रम पतन के रूप में जाना जाता है क्योंकि रोकथाम की श्रृंखला में एक भी समानता
+जटिलता की सिद्धांत में एक महत्वपूर्ण खुला प्रश्न यह है कि क्या हर NC हायरार्की में हर समावेश सही है या नहीं। पापादिमित्रियो ने यह देखा कि, यदि किसी i के लिए '''NC'''<sup>''i''</sup> = '''NC'''<sup>''i''+1</sup> है, तो '''NC'''<sup>''i''</sup> = '''NC'''<sup>''j''</sup> सभी ''j'' ≥ ''i'' के लिए होता है, और इस परिणाम के अनुसार, '''NC'''<sup>''i''</sup> = '''NC''' होता है। इस अवलोकन को '''NC'''-हायरार्की का ध्वंश कहा जाता है क्योंकि यहां समावेशों की श्रृंखला में एक ही समानता भी हो सकती है।
 :<math>\mathsf{NC}^1 \subseteq \mathsf{NC}^2 \subseteq \cdots</math>
-तात्पर्य यह है कि संपूर्ण एनसी पदानुक्रम कुछ स्तर ''i'' तक गिर जाता है। इस प्रकार, 2 संभावनाएँ हैं:
+तात्पर्य यह है कि संपूर्ण '''NC''' पदानुक्रम कुछ स्तर तक "ढह" जाता है i। इस प्रकार, 2 संभावनाएं हैं
 # <math>\mathsf{NC}^1 \subset \cdots \subset \mathsf{NC}^i \subset \cdots \subset \mathsf{NC}^{i+j} \subset \cdots \mathsf{NC}</math>
 # <math>\mathsf{NC}^1 \subset \cdots \subset \mathsf{NC}^i = \cdots = \mathsf{NC}^{i+j} = \cdots \mathsf{NC}</math>
-यह व्यापक रूप से माना जाता है कि (1) मामला है, हालांकि अभी तक किसी भी कथन की सच्चाई का कोई प्रमाण नहीं मिला है।
+यह व्यापक रूप से माना जाता है कि (1) मामला है,  चूंकि अभी तक किसी भी कथन की सच्चाई का कोई प्रमाण नहीं मिला है।
-=== एन.सी<sup>0</sup>===
+=== '''NC'''<sup>''0''</sup>===
-विशेष वर्ग एन.सी<sup>0</sup> केवल इनपुट बिट्स की एक स्थिर लंबाई पर काम करता है। इसलिए इसे निरंतर गहराई और बंधे हुए फैन-इन के साथ समान बूलियन सर्किट द्वारा परिभाषित कार्यों के वर्ग के रूप में वर्णित किया गया है।
+विशेष वर्ग '''NC'''<sup>''0''</sup> केवल इनपुट बिट्स की निरंतर लंबाई पर काम करता है। इसलिए इसे निरंतर गहराई और बंधे हुए फैन-इन के साथ समान बूलियन सर्किट द्वारा परिभाषित कार्यों के वर्ग के रूप में वर्णित किया गया है।
 == बैरिंगटन का प्रमेय ==
-चौड़ाई ''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 है। प्रोग्राम की अंतिम स्थिति में इनपुट को मैप करने वाले फ़ंक्शन को ''यील्ड' कहा जाता है '' कार्यक्रम का (अधिक सटीक रूप से, एक इनपुट पर उपज किसी भी प्रारंभिक अवस्था को संबंधित अंतिम स्थिति में मैप करने वाला फ़ंक्शन है)। कार्यक्रम ''स्वीकार करता है'' एक सेट <math>A \subset 2^n</math> चर मूल्यों का जब कार्यों का कुछ सेट होता है <math>F \subset k^k</math> जैसे कि एक चर अनुक्रम <math>x \in 2^n</math> A में है जब इसकी उपज F में है।
+चौड़ाई ''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 है। प्रोग्राम की अंतिम स्थिति में इनपुट को मैप करने वाले फ़ंक्शन को ''यील्ड' कहा जाता है '' कार्यक्रम का (अधिक सटीक रूप से, एक इनपुट पर उपज किसी भी प्रारंभिक अवस्था को संबंधित अंतिम स्थिति में मैप करने वाला फ़ंक्शन है)। कार्यक्रम ''स्वीकार करता है'' एक सेट <math>A \subset 2^n</math> चर मूल्यों का जब कार्यों का कुछ सेट होता है <math>F \subset k^k</math> जैसे कि एक चर अनुक्रम <math>x \in 2^n</math> A में है जब इसकी उपज F में है।
 शाखाओं में बंटने वाले कार्यक्रमों के एक परिवार में प्रत्येक n के लिए n चर के साथ एक शाखाकरण कार्यक्रम होता है। यह एक भाषा को तब स्वीकार करता है जब n वेरिएबल प्रोग्राम लंबाई n इनपुट तक सीमित भाषा को स्वीकार करता है।
@@ Line 57: / Line 57: @@
 यह दिखाना आसान है कि {0,1} पर प्रत्येक भाषा एल को चौड़ाई 5 और घातीय लंबाई के शाखा कार्यक्रमों के परिवार या घातीय चौड़ाई और रैखिक लंबाई के परिवार द्वारा पहचाना जा सकता है।
-{0,1} पर प्रत्येक नियमित भाषा को निरंतर चौड़ाई और निर्देशों की रैखिक संख्या के ब्रांचिंग प्रोग्राम के परिवार द्वारा पहचाना जा सकता है (चूंकि DFA को ब्रांचिंग प्रोग्राम में बदला जा सकता है)। 'बीडब्ल्यूबीपी' बंधी हुई चौड़ाई और बहुपद लंबाई के शाखा कार्यक्रमों के एक परिवार द्वारा पहचाने जाने वाली भाषाओं की श्रेणी को दर्शाता है।<ref name=CK50>Clote & Kranakis (2002) p.50</ref>
+{0,1} पर प्रत्येक नियमित भाषा को निरंतर चौड़ाई और निर्देशों की रैखिक संख्या के ब्रांचिंग प्रोग्राम के परिवार द्वारा पहचाना जा सकता है (चूंकि DFA को ब्रांचिंग प्रोग्राम में बदला जा सकता है)। BWBP सीमित चौड़ाई और बहुपद लंबाई के शाखा कार्यक्रमों के एक परिवार द्वारा पहचानी जाने वाली भाषाओं के वर्ग को दर्शाता है।<ref name=CK50>Clote & Kranakis (2002) p.50</ref>
-बैरिंगटन की प्रमेय<ref name=Bar89>{{cite journal | zbl=0667.68059 | last=Barrington | first=David A. | journal=J. Comput. Syst. Sci. | volume=38 | number=1 | pages=150–164 | year=1989 | issn=0022-0000 | url=http://www.cs.umass.edu/~barring/publications/bwbp.pdf | title=Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in '''NC'''<sup>1</sup> | doi=10.1016/0022-0000(89)90037-8| doi-access=free }}</ref> कहता है कि बीडब्ल्यूबीपी बिल्कुल [[एकरूपता (सर्किट)]] एनसी है<sup>1</उप>। प्रमाण सममित समूह S के [[हल करने योग्य समूह]] का उपयोग करता है<sub>5</sub>.<ref name=CK50/>
-प्रमेय बल्कि आश्चर्यजनक है। उदाहरण के लिए, इसका तात्पर्य है कि बहुसंख्यक कार्य की गणना निरंतर चौड़ाई और बहुपद आकार के शाखा कार्यक्रमों के एक परिवार द्वारा की जा सकती है, जबकि अंतर्ज्ञान यह सुझाव दे सकता है कि बहुपद आकार प्राप्त करने के लिए राज्यों की एक रैखिक संख्या की आवश्यकता होती है।
+बैरिंगटन की प्रमेय<ref name="Bar89">{{cite journal | zbl=0667.68059 | last=Barrington | first=David A. | journal=J. Comput. Syst. Sci. | volume=38 | number=1 | pages=150–164 | year=1989 | issn=0022-0000 | url=http://www.cs.umass.edu/~barring/publications/bwbp.pdf | title=Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in '''NC'''<sup>1</sup> | doi=10.1016/0022-0000(89)90037-8| doi-access=free }}</ref> कहता है कि BWBP बिल्कुल [[एकरूपता (सर्किट)]] '''NC'''<sup>1</sup> है।  प्रमाण सममित समूह S<sub>5</sub>के [[हल करने योग्य समूह|समाधान करने योग्य समूह]] का उपयोग करता है।<ref name="CK50" />
+प्रमेय बल्कि आश्चर्यजनक है। उदाहरण के लिए, इसका तात्पर्य है कि बहुसंख्यक कार्य की गणना निरंतर चौड़ाई और बहुपद आकार के शाखा कार्यक्रमों के एक परिवार द्वारा की जा सकती है,  चूंकि अंतर्ज्ञान यह सुझाव दे सकता है कि बहुपद आकार प्राप्त करने के लिए राज्यों की एक रैखिक संख्या की आवश्यकता होती है।
 === बैरिंगटन के प्रमेय का प्रमाण ===
-निरंतर चौड़ाई और बहुपद आकार के एक शाखा कार्यक्रम को एनसी में एक सर्किट में आसानी से परिवर्तित किया जा सकता है (विभाजन और जीत के माध्यम से)<sup>1</उप>।
+निरंतर चौड़ाई और बहुपद आकार के एक शाखा कार्यक्रम को '''NC'''<sup>1</sup>में एक सर्किट में आसानी से परिवर्तित किया जा सकता है (विभाजन और जीत के माध्यम से)।
-इसके विपरीत, एनसी में एक सर्किट मान लीजिए<sup>1</sup> दिया गया है। व्यापकता के नुकसान के बिना, मान लें कि यह केवल गेट का उपयोग करता है और नहीं।
+विपरीत रूप से, सोचें कि हमें '''NC'''<sup>1</sup> में एक सर्किट दिया गया है। उपाय की हानि के बिना, मान लें कि यह केवल AND और NOT गेट का ही उपयोग करता है।
-{{math_theorem|name=Lemma 1|If there exists a branching program that sometimes works as a permutation ''P'' and sometimes as a permutation ''Q'', by right-multiplying permutations in the first instruction by {{var|α}}, and in the last instruction left-multiplying by {{var|β}}, we can make a circuit of the same length that behaves as {{var|β}}''P''{{var|α}} or {{var|β}}''Q''{{var|α}}, respectively.}}
+{{math_theorem|name=लेम्मा 1|यदि कोई ब्रांचिंग प्रोग्राम मौजूद है जो कभी-कभी क्रमचय ''P'' के रूप में और कभी-कभी क्रमचय ''Q'' के रूप में कार्य करता है, पहले निर्देश में {{var|α}} द्वारा क्रमचय को सही-गुणा करके, और अंतिम में निर्देश बाएं- {{var|β}} से गुणा करके, हम समान लंबाई का एक सर्किट बना सकते हैं जो {{var|β}}''P''{{var|α}} या {{var|β} के रूप में व्यवहार करता है }}''Q''{{var|α}}, क्रमशः।}}
 एक ब्रांचिंग प्रोग्राम α-कंप्यूटिंग सर्किट सी को कॉल करें यदि यह पहचान के रूप में काम करता है {{var|C}} का आउटपुट 0 है, और as {{var|α}} कब {{var|C}} का आउटपुट 1 है।
-लेम्मा 1 के परिणामस्वरूप और तथ्य यह है कि लंबाई 5 के सभी चक्र [[संयुग्मन वर्ग]] हैं, किसी भी दो 5-चक्रों के लिए {{var|α}}, {{var|β}}, यदि एक सर्किट C का ब्रांचिंग प्रोग्राम α-कंप्यूटिंग मौजूद है, तो समान लंबाई का एक ब्रांचिंग प्रोग्राम β-कंप्यूटिंग सर्किट C मौजूद है।
+लेम्मा 1 के परिणामस्वरूप और तथ्य यह है कि लंबाई 5 के सभी चक्र [[संयुग्मन वर्ग]] हैं। इसलिए, किसी भी दो 5-चक्रों के लिए {{var|α}}, {{var|β}}, यदि एक सर्किट C का ब्रांचिंग प्रोग्राम α-कंप्यूटिंग  उपस्थित है, तो समान लंबाई का एक ब्रांचिंग प्रोग्राम β-कंप्यूटिंग सर्किट C  उपस्थित है।
-{{math_theorem|name=Lemma 2|1=There exist 5-cycles {{var|γ}}, {{var|δ}} such that their [[commutator]] {{math|1=''ε''=''γδγ''<sup>−1</sup>''δ''<sup>−1</sup>}} is a 5-cycle. For example, {{var|γ}} = (1 2 3 4 5), {{var|δ}} = (1 3 5 4 2) giving {{var|ε}} = (1 3 2 5 4).}}
+{{math_theorem|name=लेम्मा 2|1=5-चक्र मौजूद हैं {{var|γ}}, {{var|δ}} जैसे कि उनका [[कम्यूटेटर]] {{math|1=''ε''=''γδγ''<sup>−1 </sup>''δ''<sup>−1</sup>}} एक 5-चक्र है। उदाहरण के लिए, {{var|γ}} = (1 2 3 4 5), {{var|δ}} = (1 3 5 4 2) देने पर {{var|ε}} = (1 3 2 5 4) .}}
-{{math proof|1=We will now prove Barrington's theorem by induction:
+{{math proof|1=अब हम बैरिंगटन के प्रमेय को प्रेरण द्वारा सिद्ध करेंगे:
-Suppose we have a circuit ''C'' which takes inputs ''x''<sub>1</sub>,...,''x''<sub>''n''</sub> and assume that for all subcircuits ''D'' of ''C'' and 5-cycles α, there exists a branching program α-computing ''D''. We will show that for all 5-cycles α, there exists a branching program α-computing ''C''.
+मान लीजिए कि हमारे पास एक सर्किट ''C'' है जो इनपुट लेता है ''x''<sub>1</sub>,...,''x''<sub>''n''</sub> और मान लें कि ''C'' के सभी उपपरिपथों ''D'' और 5-चक्रों α के लिए, एक ब्रांचिंग प्रोग्राम α-कंप्यूटिंग ''D'' मौजूद है। हम दिखाएंगे कि सभी 5-चक्र α के लिए, एक ब्रांचिंग प्रोग्राम α-कंप्यूटिंग ''C'' मौजूद है।
-* If the circuit ''C'' simply outputs some input bit ''x<sub>i</sub>'', the branching program we need has just one instruction: checking {{var|x<sub>i</sub>}}'s value (0 or 1), and outputting the identity or {{var|α}} (respectively).
+* यदि सर्किट ''C'' बस कुछ इनपुट बिट ''x<sub>i</sub>'' को आउटपुट करता है, तो हमें जिस ब्रांचिंग प्रोग्राम की आवश्यकता है, उसमें केवल एक निर्देश है: चेक करना {{var|x<sub>i</ उप>}} का मान (0 या 1), और पहचान को आउटपुट करना या {{var|α}} (क्रमशः)।
-* If the circuit ''C'' outputs ¬''A'' for some different circuit ''A'', create a branching program {{var|α}}<sup>−1</sup>-computing ''A'' and then multiply the output of the program by α. By Lemma 1, we get a branching program for ''A'' outputting the identity or α, i.e. {{var|α}}-computing ¬''A''=''C''.
+* यदि सर्किट ''C'' कुछ भिन्न सर्किट ''A'' के लिए ¬''A'' आउटपुट करता है, तो एक ब्रांचिंग प्रोग्राम बनाएं {{var|α}}<sup>−1</sup>-कंप्यूटिंग '' A'' और उसके बाद प्रोग्राम के आउटपुट को α से गुणा करें। लेम्मा 1 द्वारा, हमें पहचान या α, यानी {{var|α}}-कंप्यूटिंग ¬''A''=''C'' को आउटपुट करने के लिए ''A'' के लिए एक ब्रांचिंग प्रोग्राम मिलता है।
-* If the circuit ''C'' outputs {{nowrap|''A''∧''B''}} for circuits ''A'' and ''B'', join the branching programs that {{var|γ}}-compute ''A'', {{var|δ}}-compute ''B'', {{var|γ}}<sup>−1</sup>-compute ''A'', and δ<sup>−1</sup>-compute B for a choice of 5-cycles γ and δ such that their commutator {{math|1=''ε''=''γδγ''<sup>−1</sup>''δ''<sup>−1</sup>}} is also a 5-cycle. (The existence of such elements was established in Lemma 2.) If one or both of the circuits outputs 0, the resulting program will be the identity due to cancellation; if both circuits output 1, the resulting program will output the commutator {{var|ε}}. In other words, we get a program {{var|ε}}-computing {{nowrap|''A''∧''B''}}. Because {{var|ε}} and {{var|α}} are two 5-cycles, they are conjugate, and hence there exists a program {{var|α}}-computing {{nowrap|''A''∧''B''}} by Lemma 1.
+* यदि परिपथ ''C'' परिपथ ''A'' और ''B'' के लिए {{nowrap|''A''∧''B''}} निर्गत करता है, तो {{var| γ}}-'ए' की गणना करें, {{var|δ}}-'बी' की गणना करें, {{var|γ}}<sup>−1</sup>-'ए' की गणना करें, और δ<sup>−1</sup>-5-चक्रों γ और δ के विकल्प के लिए B की गणना करें जैसे कि उनका कम्यूटेटर {{math|1=''ε''=''γδγ''<sup>−1 </sup>''δ''<sup>−1</sup>}} भी 5-चक्र है। (ऐसे तत्वों का अस्तित्व लेम्मा 2 में स्थापित किया गया था।) यदि एक या दोनों सर्किट 0 आउटपुट करते हैं, तो परिणामी प्रोग्राम रद्दीकरण के कारण पहचान होगा; यदि दोनों सर्किट आउटपुट 1 हैं, तो परिणामी प्रोग्राम कम्यूटेटर {{var|ε}} को आउटपुट करेगा। दूसरे शब्दों में, हमें {{var|ε}}-कंप्यूटिंग {{nowrap|''A''∧''B''}} प्रोग्राम मिलता है। क्योंकि {{var|ε}} और {{var|α}} दो 5-चक्र हैं, वे संयुग्मित हैं, और इसलिए एक प्रोग्राम मौजूद है {{var|α}}-कंप्यूटिंग {{nowrap|''A'' ∧''B''}} लेम्मा 1 द्वारा।
-By assuming the subcircuits have branching programs so that they are {{var|α}}-computing for all 5-cycles {{math|{{var|α}}∈''S''<sub>5</sub>}}, we have shown ''C'' also has this property, as required.
+यह मानकर कि उपपरिपथों में शाखाओं में बंटे कार्यक्रम हैं ताकि वे {{var|α}}- सभी 5-चक्रों के लिए संगणना कर सकें {{math|{{var|α}}∈''S''<sub>5</sub> }}, हमने दिखाया है कि आवश्यकता के अनुसार ''C'' में भी यह गुण है।
 }}
-ब्रांचिंग प्रोग्राम का आकार अधिकतम 4 है<sup>{{var|d}}</sup>, जहां d सर्किट की गहराई है। यदि सर्किट में लॉगरिदमिक गहराई है, तो ब्रांचिंग प्रोग्राम में बहुपद लंबाई है।
+ब्रांचिंग प्रोग्राम का आकार अधिकतम 4<sup><var>d</var></sup> है, जहाँ d सर्किट की गहराई है। यदि सर्किट में लॉगरिदमिक गहराई है, तो ब्रांचिंग प्रोग्राम में बहुपद लंबाई है।
 ==टिप्पणियाँ==

v t e Important complexity classes (more)
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

Anonymous

Search

एनसी (सम्मिश्रता): Difference between revisions

Namespaces

More

Page actions

Revision as of 10:32, 17 May 2023