View source for एसी (सम्मिश्रता)

[[सर्किट जटिलता]] में, एसी [[जटिलता वर्ग]] पदानुक्रम है। प्रत्येक वर्ग, ए.सी<sup>i</sup>, गहराई के साथ [[बूलियन सर्किट]] द्वारा मान्यता प्राप्त [[औपचारिक भाषा]] शामिल है <math>O(\log^i n)</math> और फ़ैनिन का एक [[बहुपद]] | असीमित फ़ैन-इन AND गेट और OR गेट्स।

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

एसी कक्षाओं की कुल पदानुक्रम के रूप में परिभाषित किया गया है
<ब्लॉककोट>
<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>
:<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>
यह ज्ञात है कि समावेशन i = 0 के लिए सख्त है।<ref name=AB118/>


== रूपांतर ==

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


==टिप्पणियाँ==
{{reflist}}


==संदर्भ==
*{{citation | zbl=1193.68112 | last1=Arora | first1=Sanjeev | authorlink1=Sanjeev Arora | last2=Barak | first2=Boaz | title=Computational complexity. A modern approach | publisher=[[Cambridge University Press]] | year=2009 | isbn=978-0-521-42426-4 }}
*{{citation | last1=Clote | first1=Peter | last2=Kranakis |first2=Evangelos | title=Boolean functions and computation models | series=Texts in Theoretical Computer Science. An EATCS Series | location=Berlin | publisher=[[Springer-Verlag]] | year=2002 | isbn=3-540-59436-1 | zbl=1016.94046 }}
*{{citation | last = Regan | first = Kenneth W. | contribution = Complexity classes | title = Algorithms and Theory of Computation Handbook | publisher = CRC Press | year = 1999}}.
*{{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]]