एसी (सम्मिश्रता): Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[सर्किट जटिलता|परिपथ जटिलता]] में, | [[सर्किट जटिलता|परिपथ जटिलता]] में, AC [[जटिलता वर्ग|सम्मिश्रता क्लास]] पदानुक्रम है। प्रत्येक क्लास '''AC<sup>i</sup>''' में डेप्थ <math>O(\log^i n)</math> के साथ [[बूलियन सर्किट|बूलियन]] [[सर्किट जटिलता|परिपथ]] द्वारा मान्यता प्राप्त [[औपचारिक भाषा|भाषाएं]] और असीमित फैन-इन एएनडी और ओआर गेट्स की [[बहुपद]] संख्या सम्मिलित होती है। | ||
AC को एनसी (सम्मिश्रता) के सादृश्य द्वारा चयन किया गया था, जिसमें A "अल्टेरनेटिंग" के लिए स्थायीत्व था और परिपथ में एएनडी और ओआर गेट्स के मध्य के विकल्प और ट्यूरिंग मशीनों को परिवर्तित करने के लिए संदर्भित किया गया था।<ref>{{harvtxt|Regan|1999}}, page 27-18.</ref> | |||
अतिअल्प | अतिअल्प AC क्लास AC<sup>0</sup> है, जिसमें स्थिर-डेप्थ वाले असीमित फैन-इन परिपथ सम्मिलित हैं। | ||
AC क्लासेज के कुल पदानुक्रम को <math>\mbox{AC} = \bigcup_{i \geq 0} \mbox{AC}^i</math> के रूप में परिभाषित किया गया है। | |||
'''एनसी से संबंध''' | '''एनसी से संबंध''' | ||
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> | ||
इसके शीघ्र परिणाम के रूप में, हमारे निकट एनसी = | इसके शीघ्र परिणाम के रूप में, हमारे निकट एनसी = AC है।<ref name=CK12>{{harvtxt|Clote|Kranakis|2002|p=12}}</ref> | ||
यह ज्ञात है कि समावेशन i = 0 के लिए यह अत्यधिक है।<ref name="AB118" /> | यह ज्ञात है कि समावेशन i = 0 के लिए यह अत्यधिक है।<ref name="AB118" /> | ||
| Line 19: | Line 19: | ||
== रूपांतर == | == रूपांतर == | ||
अतिरिक्त गेट्स को जोड़कर | अतिरिक्त गेट्स को जोड़कर AC क्लासेज की शक्ति प्रभावित हो सकती है। यदि हम गेट्स जोड़ते हैं जो कुछ मॉड्यूलस एम के लिए [[मॉड्यूल ऑपरेशन]] की गणना करते हैं, तो हमारे निकट ACसीआई [एम] क्लासेज होती हैं।<ref name=CK12/> | ||
| Line 31: | Line 31: | ||
*{{citation | last = Regan | first = Kenneth W. | contribution = Complexity classes | title = Algorithms and Theory of Computation Handbook | publisher = CRC Press | year = 1999}}. | *{{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 }} | *{{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 }} | ||
[[Category: सर्किट जटिलता]] [[Category: जटिलता वर्ग]] | [[Category: सर्किट जटिलता]] [[Category: जटिलता वर्ग]] | ||
Revision as of 16:17, 24 May 2023
परिपथ जटिलता में, AC सम्मिश्रता क्लास पदानुक्रम है। प्रत्येक क्लास ACi में डेप्थ के साथ बूलियन परिपथ द्वारा मान्यता प्राप्त भाषाएं और असीमित फैन-इन एएनडी और ओआर गेट्स की बहुपद संख्या सम्मिलित होती है।
AC को एनसी (सम्मिश्रता) के सादृश्य द्वारा चयन किया गया था, जिसमें A "अल्टेरनेटिंग" के लिए स्थायीत्व था और परिपथ में एएनडी और ओआर गेट्स के मध्य के विकल्प और ट्यूरिंग मशीनों को परिवर्तित करने के लिए संदर्भित किया गया था।[1]
अतिअल्प AC क्लास AC0 है, जिसमें स्थिर-डेप्थ वाले असीमित फैन-इन परिपथ सम्मिलित हैं।
AC क्लासेज के कुल पदानुक्रम को के रूप में परिभाषित किया गया है।
एनसी से संबंध
AC क्लासेज एनसी (सम्मिश्रता) क्लासेज से संबंधित होती हैं, जिन्हें समान रूप से परिभाषित किया गया है, किन्तु गेट्स के साथ मात्र स्थिर फ़ैनिन होता है। प्रत्येक i के लिए, हमारे निकट है-[2][3]
इसके शीघ्र परिणाम के रूप में, हमारे निकट एनसी = AC है।[4]
यह ज्ञात है कि समावेशन i = 0 के लिए यह अत्यधिक है।[3]
रूपांतर
अतिरिक्त गेट्स को जोड़कर AC क्लासेज की शक्ति प्रभावित हो सकती है। यदि हम गेट्स जोड़ते हैं जो कुछ मॉड्यूलस एम के लिए मॉड्यूल ऑपरेशन की गणना करते हैं, तो हमारे निकट ACसीआई [एम] क्लासेज होती हैं।[4]
टिप्पणियाँ
- ↑ Regan (1999), page 27-18.
- ↑ Clote & Kranakis (2002, p. 437)
- ↑ 3.0 3.1 Arora & Barak (2009, p. 118)
- ↑ 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
