टीसी (सम्मिश्रता): Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[सैद्धांतिक कंप्यूटर विज्ञान]] और विशेष रूप से [[कम्प्यूटेशनल जटिलता सिद्धांत]] और [[सर्किट जटिलता]] में, टीसी [[निर्णय समस्या]] का एक [[जटिलता वर्ग]] है जिसे | [[सैद्धांतिक कंप्यूटर विज्ञान]] और विशेष रूप से [[कम्प्यूटेशनल जटिलता सिद्धांत]] और [[सर्किट जटिलता]] में, टीसी [[निर्णय समस्या]] का एक [[जटिलता वर्ग]] है जिसे सीमांकित सर्किट द्वारा पहचाना जा सकता है, जो [[ तथा द्वार |तथा द्वार]] , या गेट और अधिकांश द्वार वाले [[बूलियन सर्किट]] होते हैं। प्रत्येक नियत ''i'' के लिए,TC<sup>i</sup> जटिलता वर्ग सभी भाषाओं से मिलकर बनता है जो एक थ्रेशोल्ड सर्किट परिवार द्वारा पहचानी जा सकती हैं जिनकी गहराई <math>O(\log^i n)</math>, [[बहुपद]] आकार, और असीमित [[ प्रशंसक में |प्रशंसक]] होती है। र्ग TC को निम्नलिखित रूप में परिभाषित किया जाता है। | ||
:<math>\mbox{TC} = \bigcup_{i \geq 0} \mbox{TC}^i.</math> | :<math>\mbox{TC} = \bigcup_{i \geq 0} \mbox{TC}^i.</math> | ||
| Line 7: | Line 7: | ||
विशेष रूप से, हम यह जानते हैं | विशेष रूप से, हम यह जानते हैं | ||
:<math>\mbox{NC}^0 \subsetneq \mbox{AC}^0 \subsetneq \mbox{TC}^0 \subseteq \mbox{NC}^{1}.</math> | :<math>\mbox{NC}^0 \subsetneq \mbox{AC}^0 \subsetneq \mbox{TC}^0 \subseteq \mbox{NC}^{1}.</math> | ||
पहली | पहली सख्त अवधारणा उस तथ्य से होती है कि '''NC<sup>0</sup>''' कोई भी ऐसा फ़ंक्शन नहीं पूर्ण कर सकता है जो सभी इनपुट बिट पर निर्भर करता है। इसलिए, उन्हें एक ऐसी समस्या चुनना चाहिए जो '''AC<sup>0</sup>''' में स्पष्ट रूप से होती है और सभी बिट पर निर्भर करती है (उदाहरण के लिए, OR फ़ंक्शन का विचार करें)। '''AC<sup>0</sup>''' ⊊ '''TC<sup>0</sup>''' की सख्त अवधारणा उनके कारण होती है कि पॅरिटी और मेज़ॉरिटी (जो दोनों '''TC<sup>0</sup>''' में हैं) को '''AC<sup>0</sup>''' में नहीं माना गया था <sup>।<ref>{{citation | last1 = Furst | first1 = Merrick | last2 = Saxe | first2 = James B. | author2-link = James B. Saxe | last3 = Sipser | first3 = Michael | author3-link = Michael Sipser | doi = 10.1007/BF01744431 | issue = 1 | journal = Mathematical Systems Theory | mr = 738749 | pages = 13–27 | title = Parity, circuits, and the polynomial-time hierarchy | volume = 17 | year = 1984}}.</ref><ref>{{Citation | last1=Håstad | first1=Johan | series=Advances in Computing Research | volume=5 | title=Randomness and Computation | editor-first=Silvio | editor-last=Micali | url=http://reference.kfupm.edu.sa/content/a/l/almost_optimal_lower_bounds_for_small_de_134215.pdf | publisher=JAI Press | year=1989 | chapter=Almost Optimal Lower Bounds for Small Depth Circuits | pages=6–20 | isbn=0-89232-896-7 | url-status=dead | archiveurl=https://web.archive.org/web/20120222163102/http://reference.kfupm.edu.sa/content/a/l/almost_optimal_lower_bounds_for_small_de_134215.pdf | archivedate=2012-02-22 }}</ref> | ||
उपरोक्त नियंत्रणों के तत्काल परिणाम के रूप में, हमारे पास NC = AC = TC है। | उपरोक्त नियंत्रणों के तत्काल परिणाम के रूप में, हमारे पास NC = AC = TC है। | ||
Revision as of 15:28, 17 May 2023
सैद्धांतिक कंप्यूटर विज्ञान और विशेष रूप से कम्प्यूटेशनल जटिलता सिद्धांत और सर्किट जटिलता में, टीसी निर्णय समस्या का एक जटिलता वर्ग है जिसे सीमांकित सर्किट द्वारा पहचाना जा सकता है, जो तथा द्वार , या गेट और अधिकांश द्वार वाले बूलियन सर्किट होते हैं। प्रत्येक नियत i के लिए,TCi जटिलता वर्ग सभी भाषाओं से मिलकर बनता है जो एक थ्रेशोल्ड सर्किट परिवार द्वारा पहचानी जा सकती हैं जिनकी गहराई , बहुपद आकार, और असीमित प्रशंसक होती है। र्ग TC को निम्नलिखित रूप में परिभाषित किया जाता है।
NC और AC से संबंध
टीसी, एनसी (जटिलता) और एसी (जटिलता) पदानुक्रम के बीच संबंध को निम्नानुसार संक्षेपित किया जा सकता है:
विशेष रूप से, हम यह जानते हैं
पहली सख्त अवधारणा उस तथ्य से होती है कि NC0 कोई भी ऐसा फ़ंक्शन नहीं पूर्ण कर सकता है जो सभी इनपुट बिट पर निर्भर करता है। इसलिए, उन्हें एक ऐसी समस्या चुनना चाहिए जो AC0 में स्पष्ट रूप से होती है और सभी बिट पर निर्भर करती है (उदाहरण के लिए, OR फ़ंक्शन का विचार करें)। AC0 ⊊ TC0 की सख्त अवधारणा उनके कारण होती है कि पॅरिटी और मेज़ॉरिटी (जो दोनों TC0 में हैं) को AC0 में नहीं माना गया था ।[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.
