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

Unsolved problem in computer science:

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

(more unsolved problems in computer science)

कम्प्यूटेशनल जटिलता सिद्धांत में, कक्षा एनसी (निक की कक्षा के लिए) प्रोसेसर की बहुपद संख्या के साथ समांतर कंप्यूटिंग पर पॉलीलॉगरिदमिक समय में निर्णय लेने योग्य निर्णय समस्याओं का सेट है। दूसरे शब्दों में, इनपुट आकार n के साथ एक समस्या NC में है यदि स्थिरांक c और k मौजूद हैं जैसे कि इसे समय पर हल किया जा सकता है O((log n)^c) का उपयोग करना O(n^k) समानांतर प्रोसेसर। स्टीफन कुक निक की कक्षा का नाम निक पिपेंजर के नाम पर रखा गया, जिन्होंने व्यापक शोध किया था बहुलगणकीय गहराई और बहुपद आकार वाले परिपथों पर। जिस तरह क्लास पी (जटिलता) को ट्रैक्टेबल प्रॉब्लम्स (कोभम की थीसिस) के रूप में सोचा जा सकता है, उसी तरह एनसी को उन समस्याओं के रूप में सोचा जा सकता है जिन्हें एक समानांतर कंप्यूटर पर कुशलता से हल किया जा सकता है। NC, P का एक उपसमुच्चय है क्योंकि बहुलगणक समांतर संगणनाओं को बहुपद-समय अनुक्रमिक द्वारा सिम्युलेट किया जा सकता है। यह अज्ञात है कि क्या एनसी = पी, लेकिन अधिकांश शोधकर्ताओं को संदेह है कि यह झूठा है, जिसका अर्थ है कि शायद कुछ ट्रैक्टेबल समस्याएं हैं जो स्वाभाविक रूप से अनुक्रमिक हैं और समांतरता का उपयोग करके महत्वपूर्ण रूप से तेज नहीं हो सकती हैं। जिस तरह एनपी-पूर्ण वर्ग को शायद अट्रैक्टिव माना जा सकता है, उसी तरह एनसी रिडक्शन का उपयोग करते समय क्लास एन पी-सम्पूर्ण को शायद समानांतर या शायद स्वाभाविक रूप से अनुक्रमिक नहीं माना जा सकता है।

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

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

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

== एनसी == में समस्याएं पी के साथ, भाषा के थोड़े से दुरुपयोग से, कोई भी कार्य समस्याओं को वर्गीकृत कर सकता है और एनसी में होने वाली समस्याओं को खोज सकता है। नेकां सहित कई समस्याओं को शामिल करने के लिए जाना जाता है

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

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

उदाहरण

नेकां में समस्या का एक उदाहरण¹ बिट स्ट्रिंग पर पैरिटी चेक है। समस्या 1 और 0 से बनी एक स्ट्रिंग में 1s की संख्या की गणना करने में होती है। एक सरल समाधान में स्ट्रिंग के सभी बिट्स का योग होता है। क्योंकि योग साहचर्य है, $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})$.

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

एनसीⁱ अधिक से अधिक दो इनपुट और गहराई वाले गेटों की बहुपद संख्या के साथ यूनिफ़ॉर्म बूलियन सर्किट द्वारा तय की जाने वाली निर्णय समस्याओं का वर्ग है 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 के लिए सख्त हैं।

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

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

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

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

तात्पर्य यह है कि संपूर्ण एनसी पदानुक्रम कुछ स्तर 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) मामला है, हालांकि अभी तक किसी भी कथन की सच्चाई का कोई प्रमाण नहीं मिला है।

एन.सी⁰

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

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

चौड़ाई 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 को ब्रांचिंग प्रोग्राम में बदला जा सकता है)। 'बीडब्ल्यूबीपी' बंधी हुई चौड़ाई और बहुपद लंबाई के शाखा कार्यक्रमों के एक परिवार द्वारा पहचाने जाने वाली भाषाओं की श्रेणी को दर्शाता है। बैरिंगटन की प्रमेय कहता है कि बीडब्ल्यूबीपी बिल्कुल एकरूपता (सर्किट) एनसी है^{1</उप>। प्रमाण सममित समूह S के हल करने योग्य समूह का उपयोग करता है₅.}

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

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

निरंतर चौड़ाई और बहुपद आकार के एक शाखा कार्यक्रम को एनसी में एक सर्किट में आसानी से परिवर्तित किया जा सकता है (विभाजन और जीत के माध्यम से)^{1</उप>।}

इसके विपरीत, एनसी में एक सर्किट मान लीजिए¹ दिया गया है। व्यापकता के नुकसान के बिना, मान लें कि यह केवल गेट का उपयोग करता है और नहीं।

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 α, and in the last instruction left-multiplying by β, we can make a circuit of the same length that behaves as βPα or βQα, respectively.

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

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

Lemma 2 — There exist 5-cycles γ, δ such that their commutator ε=γδγ⁻¹δ⁻¹ is a 5-cycle. For example, γ = (1 2 3 4 5), δ = (1 3 5 4 2) giving ε = (1 3 2 5 4).

Proof

We will now prove Barrington's theorem by induction:

Suppose we have a circuit C which takes inputs x₁,...,x_n 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.

• If the circuit C simply outputs some input bit x_i, the branching program we need has just one instruction: checking x_i's value (0 or 1), and outputting the identity or α (respectively).
• If the circuit C outputs ¬A for some different circuit A, create a branching program α⁻¹-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. α-computing ¬A=C.
• If the circuit C outputs A∧B for circuits A and B, join the branching programs that γ-compute A, δ-compute B, γ⁻¹-compute A, and δ⁻¹-compute B for a choice of 5-cycles γ and δ such that their commutator ε=γδγ⁻¹δ⁻¹ 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 ε. In other words, we get a program ε-computing A∧B. Because ε and α are two 5-cycles, they are conjugate, and hence there exists a program α-computing A∧B by Lemma 1.

By assuming the subcircuits have branching programs so that they are α-computing for all 5-cycles α∈S₅, we have shown C also has this property, as required.

ब्रांचिंग प्रोग्राम का आकार अधिकतम 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.