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

From Vigyanwiki
No edit summary
No edit summary
 
(7 intermediate revisions by 5 users not shown)
Line 1: Line 1:
[[सर्किट जटिलता|परिपथ जटिलता]] में, एसी [[जटिलता वर्ग|सम्मिश्रता क्लास]] पदानुक्रम है। प्रत्येक क्लास एसी<sup>i</sup> में डेप्थ <math>O(\log^i n)</math> के साथ [[बूलियन सर्किट|बूलियन]] [[सर्किट जटिलता|परिपथ]] द्वारा मान्यता प्राप्त [[औपचारिक भाषा|भाषाएं]] और असीमित फैन-इन एएनडी और ओआर गेट्स की [[बहुपद]] संख्या सम्मिलित होती है।
[[सर्किट जटिलता|परिपथ जटिलता]] में, '''एसी (AC)''' [[जटिलता वर्ग|सम्मिश्रता क्लास]] पदानुक्रम है। प्रत्येक क्लास '''AC<sup>i</sup>''' में डेप्थ <math>O(\log^i n)</math> के साथ [[बूलियन सर्किट|बूलियन]] [[सर्किट जटिलता|परिपथ]] द्वारा मान्यता प्राप्त [[औपचारिक भाषा|भाषाएं]] और असीमित फैन-इन एएनडी और ओआर गेट्स की [[बहुपद]] संख्या सम्मिलित होती है।


एसी को एनसी (सम्मिश्रता) के सादृश्य द्वारा चुना गया था, नाम में A के साथ बारी-बारी से खड़े होने और सर्किट में AND और OR गेट्स के बीच के विकल्प और ट्यूरिंग मशीनों को बदलने के लिए संदर्भित किया गया था।<ref>{{harvtxt|Regan|1999}}, page 27-18.</ref>
AC को एनसी (सम्मिश्रता) के सादृश्य द्वारा चयन किया गया था, जिसमें A "अल्टेरनेटिंग" के लिए स्थायीत्व था और परिपथ में एएनडी और ओआर गेट्स के मध्य के विकल्प और ट्यूरिंग मशीनों को परिवर्तित करने के लिए संदर्भित किया गया था।<ref>{{harvtxt|Regan|1999}}, page 27-18.</ref>
सबसे छोटा एसी क्लास AC0|AC है<sup>0</sup>, जिसमें निरंतर-गहराई वाले असीमित फैन-इन सर्किट शामिल हैं।


एसी कक्षाओं की कुल पदानुक्रम के रूप में परिभाषित किया गया है
अतिअल्प AC क्लास AC<sup>0</sup> है, जिसमें स्थिर-डेप्थ वाले असीमित फैन-इन परिपथ सम्मिलित हैं।
<ब्लॉककोट>
<math>\mbox{AC} = \bigcup_{i \geq 0} \mbox{AC}^i</math> </ब्लॉककोट>


== एनसी == से संबंध
AC क्लासेज के कुल पदानुक्रम को <math>\mbox{AC} = \bigcup_{i \geq 0} \mbox{AC}^i</math> के रूप में परिभाषित किया गया है।
एसी कक्षाएं एनसी (जटिलता) वर्गों से संबंधित हैं, जिन्हें समान रूप से परिभाषित किया गया है, लेकिन फाटकों के साथ केवल निरंतर फ़ैनिन होता है। प्रत्येक i के लिए, हमारे पास है<ref name=CK437>{{harvtxt|Clote|Kranakis|2002|p=437}}</ref><ref name=AB118>{{harvtxt|Arora|Barak|2009|p=118}}</ref>
 
'''एनसी से संबंध'''
 
AC क्लासेज एनसी (सम्मिश्रता) क्लासेज से संबंधित होती हैं, जिन्हें समान रूप से परिभाषित किया गया है, किन्तु गेट्स के साथ मात्र स्थिर फ़ैनिन होता है। प्रत्येक i के लिए, हमारे निकट है-<ref name="CK437">{{harvtxt|Clote|Kranakis|2002|p=437}}</ref><ref name="AB118">{{harvtxt|Arora|Barak|2009|p=118}}</ref>
:<math>\mbox{NC}^i \subseteq \mbox{AC}^i \subseteq \mbox{NC}^{i+1}.</math>
:<math>\mbox{NC}^i \subseteq \mbox{AC}^i \subseteq \mbox{NC}^{i+1}.</math>
इसके तत्काल परिणाम के रूप में, हमारे पास वह NC = AC है।<ref name=CK12>{{harvtxt|Clote|Kranakis|2002|p=12}}</ref>
इसके शीघ्र परिणाम के रूप में, हमारे निकट एनसी = AC है।<ref name=CK12>{{harvtxt|Clote|Kranakis|2002|p=12}}</ref>
यह ज्ञात है कि समावेशन i = 0 के लिए सख्त है।<ref name=AB118/>
 
यह ज्ञात है कि समावेशन i = 0 के लिए यह अत्यधिक है।<ref name="AB118" />
 




== रूपांतर ==
== रूपांतर ==


अतिरिक्त फाटकों को जोड़कर एसी कक्षाओं की शक्ति प्रभावित हो सकती है। यदि हम गेट्स जोड़ते हैं जो कुछ मॉड्यूलस एम के लिए [[मॉड्यूल ऑपरेशन]] की गणना करते हैं, तो हमारे पास वर्ग एसीसी (जटिलता) | एसीसी है<sup>मैं</sup>[एम]।<ref name=CK12/>
अतिरिक्त गेट्स को जोड़कर AC क्लासेज की शक्ति प्रभावित हो सकती है। यदि हम गेट्स जोड़ते हैं जो कुछ मॉड्यूलस एम के लिए [[मॉड्यूल ऑपरेशन]] की गणना करते हैं, तो हमारे निकट ACसीआई [एम] क्लासेज होती हैं।<ref name=CK12/>




Line 30: Line 32:
*{{citation | last=Vollmer | first=Heribert | title=Introduction to circuit complexity. A uniform approach | series=Texts in Theoretical Computer Science | location=Berlin | publisher=[[Springer-Verlag]] | year=1998 | isbn=3-540-64310-9 | zbl=0931.68055 }}
*{{citation | last=Vollmer | first=Heribert | title=Introduction to circuit complexity. A uniform approach | series=Texts in Theoretical Computer Science | location=Berlin | publisher=[[Springer-Verlag]] | year=1998 | isbn=3-540-64310-9 | zbl=0931.68055 }}


{{ComplexityClasses}}
[[Category: सर्किट जटिलता]] [[Category: जटिलता वर्ग]]
[[Category: Machine Translated Page]]
[[Category:Created On 12/05/2023]]
[[Category:Created On 12/05/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:जटिलता वर्ग]]
[[Category:सर्किट जटिलता]]

Latest revision as of 16:11, 30 October 2023

परिपथ जटिलता में, एसी (AC) सम्मिश्रता क्लास पदानुक्रम है। प्रत्येक क्लास ACi में डेप्थ के साथ बूलियन परिपथ द्वारा मान्यता प्राप्त भाषाएं और असीमित फैन-इन एएनडी और ओआर गेट्स की बहुपद संख्या सम्मिलित होती है।

AC को एनसी (सम्मिश्रता) के सादृश्य द्वारा चयन किया गया था, जिसमें A "अल्टेरनेटिंग" के लिए स्थायीत्व था और परिपथ में एएनडी और ओआर गेट्स के मध्य के विकल्प और ट्यूरिंग मशीनों को परिवर्तित करने के लिए संदर्भित किया गया था।[1]

अतिअल्प AC क्लास AC0 है, जिसमें स्थिर-डेप्थ वाले असीमित फैन-इन परिपथ सम्मिलित हैं।

AC क्लासेज के कुल पदानुक्रम को के रूप में परिभाषित किया गया है।

एनसी से संबंध

AC क्लासेज एनसी (सम्मिश्रता) क्लासेज से संबंधित होती हैं, जिन्हें समान रूप से परिभाषित किया गया है, किन्तु गेट्स के साथ मात्र स्थिर फ़ैनिन होता है। प्रत्येक i के लिए, हमारे निकट है-[2][3]

इसके शीघ्र परिणाम के रूप में, हमारे निकट एनसी = AC है।[4]

यह ज्ञात है कि समावेशन i = 0 के लिए यह अत्यधिक है।[3]


रूपांतर

अतिरिक्त गेट्स को जोड़कर AC क्लासेज की शक्ति प्रभावित हो सकती है। यदि हम गेट्स जोड़ते हैं जो कुछ मॉड्यूलस एम के लिए मॉड्यूल ऑपरेशन की गणना करते हैं, तो हमारे निकट ACसीआई [एम] क्लासेज होती हैं।[4]


टिप्पणियाँ

  1. ↑ Regan (1999), page 27-18.
  2. ↑ Clote & Kranakis (2002, p. 437)
  3. ↑ 3.0 3.1 Arora & Barak (2009, p. 118)
  4. ↑ 4.0 4.1 Clote & Kranakis (2002, p. 12)


संदर्भ

  • 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
  • Regan, Kenneth W. (1999), "Complexity classes", Algorithms and Theory of Computation Handbook, CRC Press.
  • 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
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=एसी_(सम्मिश्रता)&oldid=271677’