टीसी (सम्मिश्रता): Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[सैद्धांतिक कंप्यूटर विज्ञान]] और विशेष रूप से [[कम्प्यूटेशनल जटिलता सिद्धांत]] और [[सर्किट जटिलता]] में, टीसी [[निर्णय समस्या]] का एक [[जटिलता वर्ग]] है जिसे थ्रेशोल्ड सर्किट द्वारा पहचाना जा सकता है, जो [[ तथा द्वार ]], या गेट और अधिकांश गेट्स के साथ [[बूलियन सर्किट]] हैं। प्रत्येक नियत ''i'' के लिए, जटिलता वर्ग TC<sup>i</sup> में वे सभी भाषाएँ शामिल हैं जिन्हें गहराई के थ्रेशोल्ड सर्किट के परिवार द्वारा पहचाना जा सकता है <math>O(\log^i n)</math>, [[बहुपद]] आकार, और असीमित [[ प्रशंसक में ]]। वर्ग टीसी के माध्यम से परिभाषित किया गया है | [[सैद्धांतिक कंप्यूटर विज्ञान]] और विशेष रूप से [[कम्प्यूटेशनल जटिलता सिद्धांत]] और [[सर्किट जटिलता]] में, टीसी [[निर्णय समस्या]] का एक [[जटिलता वर्ग]] है जिसे थ्रेशोल्ड सर्किट द्वारा पहचाना जा सकता है, जो [[ तथा द्वार |तथा द्वार]] , या गेट और अधिकांश गेट्स के साथ [[बूलियन सर्किट]] हैं। प्रत्येक नियत ''i'' के लिए, जटिलता वर्ग TC<sup>i</sup> में वे सभी भाषाएँ शामिल हैं जिन्हें गहराई के थ्रेशोल्ड सर्किट के परिवार द्वारा पहचाना जा सकता है <math>O(\log^i n)</math>, [[बहुपद]] आकार, और असीमित [[ प्रशंसक में |प्रशंसक में]] । वर्ग टीसी के माध्यम से परिभाषित किया गया है | ||
:<math>\mbox{TC} = \bigcup_{i \geq 0} \mbox{TC}^i.</math> | :<math>\mbox{TC} = \bigcup_{i \geq 0} \mbox{TC}^i.</math> | ||
== एनसी और एसी == से संबंध | == एनसी और एसी == से संबंध टीसी, एनसी (जटिलता) और [[एसी (जटिलता)]] पदानुक्रम के बीच संबंध को निम्नानुसार संक्षेपित किया जा सकता है: | ||
टीसी, एनसी (जटिलता) और [[एसी (जटिलता)]] पदानुक्रम के बीच संबंध को निम्नानुसार संक्षेपित किया जा सकता है: | |||
:<math>\mbox{NC}^i \subseteq \mbox{AC}^i \subseteq \mbox{TC}^i \subseteq \mbox{NC}^{i+1}.</math> | :<math>\mbox{NC}^i \subseteq \mbox{AC}^i \subseteq \mbox{TC}^i \subseteq \mbox{NC}^{i+1}.</math> | ||
विशेष रूप से, हम यह जानते हैं | विशेष रूप से, हम यह जानते हैं | ||
Revision as of 12:34, 17 May 2023
सैद्धांतिक कंप्यूटर विज्ञान और विशेष रूप से कम्प्यूटेशनल जटिलता सिद्धांत और सर्किट जटिलता में, टीसी निर्णय समस्या का एक जटिलता वर्ग है जिसे थ्रेशोल्ड सर्किट द्वारा पहचाना जा सकता है, जो तथा द्वार , या गेट और अधिकांश गेट्स के साथ बूलियन सर्किट हैं। प्रत्येक नियत i के लिए, जटिलता वर्ग TCi में वे सभी भाषाएँ शामिल हैं जिन्हें गहराई के थ्रेशोल्ड सर्किट के परिवार द्वारा पहचाना जा सकता है , बहुपद आकार, और असीमित प्रशंसक में । वर्ग टीसी के माध्यम से परिभाषित किया गया है
== एनसी और एसी == से संबंध टीसी, एनसी (जटिलता) और एसी (जटिलता) पदानुक्रम के बीच संबंध को निम्नानुसार संक्षेपित किया जा सकता है:
विशेष रूप से, हम यह जानते हैं
पहली कड़ी रोकथाम इस तथ्य से होती है कि NC0 किसी भी फ़ंक्शन की गणना नहीं कर सकता जो सभी इनपुट बिट्स पर निर्भर करता है। इस प्रकार ऐसी समस्या का चयन करना जो एसी में तुच्छ हो0 और सभी बिट्स पर निर्भर करता है दो वर्गों को अलग करता है। (उदाहरण के लिए, OR फ़ंक्शन पर विचार करें।) सख्त नियंत्रण एसी0 ⊊ टीसी0 आता है क्योंकि समता और बहुमत (जो दोनों टीसी में हैं0) को AC में नहीं दिखाया गया था ।[1][2]
उपरोक्त नियंत्रणों के तत्काल परिणाम के रूप में, हमारे पास NC = AC = TC है।
संदर्भ
- ↑ Furst, Merrick; Saxe, James B.; Sipser, Michael (1984), "Parity, circuits, and the polynomial-time hierarchy", Mathematical Systems Theory, 17 (1): 13–27, doi:10.1007/BF01744431, MR 0738749.
- ↑ Håstad, Johan (1989), "Almost Optimal Lower Bounds for Small Depth Circuits", in Micali, Silvio (ed.), Randomness and Computation (PDF), Advances in Computing Research, vol. 5, JAI Press, pp. 6–20, ISBN 0-89232-896-7, archived from the original (PDF) on 2012-02-22
- Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 3-540-64310-9.
