टीसी (सम्मिश्रता): Difference between revisions
From Vigyanwiki
m (Abhishek moved page टीसी (जटिलता) to टीसी (सम्मिश्रता) without leaving a redirect) |
(→संदर्भ) |
||
| (9 intermediate revisions by 4 users not shown) | |||
| 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> | ||
== NC और AC से संबंध == | |||
== | |||
टीसी, एनसी (जटिलता) और [[एसी (जटिलता)]] पदानुक्रम के बीच संबंध को निम्नानुसार संक्षेपित किया जा सकता है: | टीसी, एनसी (जटिलता) और [[एसी (जटिलता)]] पदानुक्रम के बीच संबंध को निम्नानुसार संक्षेपित किया जा सकता है: | ||
:<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> | ||
विशेष रूप से, हम यह जानते हैं | विशेष रूप से, हम यह जानते हैं | ||
:<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 है। | ||
==संदर्भ== | ==संदर्भ== | ||
{{reflist}} | {{reflist}} | ||
*{{cite book | last = Vollmer | first = Heribert | title = Introduction to Circuit Complexity | year = 1999 | publisher = Springer | location | *{{cite book | last = Vollmer | first = Heribert | title = Introduction to Circuit Complexity | year = 1999 | publisher = Springer | location | ||
[[Category: | [[Category:Collapse templates]] | ||
[[Category:Created On 12/05/2023]] | [[Category:Created On 12/05/2023]] | ||
[[Category:Machine Translated Page]] | |||
[[Category:Navigational boxes| ]] | |||
[[Category:Navigational boxes without horizontal lists]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Sidebars with styles needing conversion]] | |||
[[Category:Template documentation pages|Documentation/doc]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates generating microformats]] | |||
[[Category:Templates that are not mobile friendly]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:Wikipedia metatemplates]] | |||
[[Category:जटिलता वर्ग]] | |||
[[Category:सर्किट जटिलता]] | |||
Latest revision as of 16:09, 26 October 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
- {{cite book | last = Vollmer | first = Heribert | title = Introduction to Circuit Complexity | year = 1999 | publisher = Springer | location
