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

परिपथ जटिलता में, एसी सम्मिश्रता क्लास पदानुक्रम है। प्रत्येक क्लास एसीⁱ में डेप्थ $O(\log ^{i}n)$ के साथ बूलियन परिपथ द्वारा मान्यता प्राप्त भाषाएं और असीमित फैन-इन एएनडी और ओआर गेट्स की बहुपद संख्या सम्मिलित होती है।

एसी को एनसी (सम्मिश्रता) के सादृश्य द्वारा चुना गया था, नाम में A के साथ बारी-बारी से खड़े होने और सर्किट में AND और OR गेट्स के बीच के विकल्प और ट्यूरिंग मशीनों को बदलने के लिए संदर्भित किया गया था। सबसे छोटा एसी क्लास AC0|AC है⁰, जिसमें निरंतर-गहराई वाले असीमित फैन-इन सर्किट शामिल हैं।

एसी कक्षाओं की कुल पदानुक्रम के रूप में परिभाषित किया गया है <ब्लॉककोट> ${\mbox{AC}}=\bigcup _{i\geq 0}{\mbox{AC}}^{i}$ </ब्लॉककोट>

== एनसी == से संबंध एसी कक्षाएं एनसी (जटिलता) वर्गों से संबंधित हैं, जिन्हें समान रूप से परिभाषित किया गया है, लेकिन फाटकों के साथ केवल निरंतर फ़ैनिन होता है। प्रत्येक i के लिए, हमारे पास है

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

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

रूपांतर

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

संदर्भ

• 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