टीसी (सम्मिश्रता): Difference between revisions
m (Abhishek moved page टीसी (जटिलता) to टीसी (सम्मिश्रता) without leaving a redirect) |
No edit summary |
||
| Line 8: | Line 8: | ||
विशेष रूप से, हम यह जानते हैं | विशेष रूप से, हम यह जानते हैं | ||
:<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> किसी भी फ़ंक्शन की गणना नहीं कर सकता जो सभी इनपुट बिट्स पर निर्भर करता है। इस प्रकार ऐसी समस्या का चयन करना जो एसी में तुच्छ हो<sup>0</sup> और सभी बिट्स पर निर्भर करता है दो वर्गों को अलग करता है। (उदाहरण के लिए, OR फ़ंक्शन पर विचार करें।) सख्त नियंत्रण एसी<sup>0</sup> ⊊ टीसी<sup>0</sup> आता है क्योंकि समता और बहुमत (जो दोनों टीसी में हैं<sup>0</sup>) को AC में नहीं दिखाया गया था<sup | पहली कड़ी रोकथाम इस तथ्य से होती है कि NC<sup>0</sup> किसी भी फ़ंक्शन की गणना नहीं कर सकता जो सभी इनपुट बिट्स पर निर्भर करता है। इस प्रकार ऐसी समस्या का चयन करना जो एसी में तुच्छ हो<sup>0</sup> और सभी बिट्स पर निर्भर करता है दो वर्गों को अलग करता है। (उदाहरण के लिए, OR फ़ंक्शन पर विचार करें।) सख्त नियंत्रण एसी<sup>0</sup> ⊊ टीसी<sup>0</sup> आता है क्योंकि समता और बहुमत (जो दोनों टीसी में हैं<sup>0</sup>) को AC में नहीं दिखाया गया था <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 12:30, 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.
