टीसी (सम्मिश्रता)

सैद्धांतिक कंप्यूटर विज्ञान और विशेष रूप से कम्प्यूटेशनल जटिलता सिद्धांत और सर्किट जटिलता में, टीसी निर्णय समस्या का एक जटिलता वर्ग है जिसे सीमांकित सर्किट द्वारा पहचाना जा सकता है, जो तथा द्वार , या गेट और अधिकांश द्वार वाले बूलियन सर्किट होते हैं। प्रत्येक नियत i के लिए,TCⁱ जटिलता वर्ग सभी भाषाओं से मिलकर बनता है जो एक थ्रेशोल्ड सर्किट परिवार द्वारा पहचानी जा सकती हैं जिनकी गहराई $O(\log ^{i}n)$, बहुपद आकार, और असीमित प्रशंसक होती है। वर्ग TC को निम्नलिखित रूप में परिभाषित किया जाता है।

${\mbox{TC}}=\bigcup _{i\geq 0}{\mbox{TC}}^{i}.$

NC और AC से संबंध

टीसी, एनसी (जटिलता) और एसी (जटिलता) पदानुक्रम के बीच संबंध को निम्नानुसार संक्षेपित किया जा सकता है:

${\mbox{NC}}^{i}\subseteq {\mbox{AC}}^{i}\subseteq {\mbox{TC}}^{i}\subseteq {\mbox{NC}}^{i+1}.$

विशेष रूप से, हम यह जानते हैं

${\mbox{NC}}^{0}\subsetneq {\mbox{AC}}^{0}\subsetneq {\mbox{TC}}^{0}\subseteq {\mbox{NC}}^{1}.$

पहली सख्त अवधारणा उस तथ्य से होती है कि NC⁰ कोई भी ऐसा फ़ंक्शन नहीं पूर्ण कर सकता है जो सभी इनपुट बिट पर निर्भर करता है। इसलिए, उन्हें एक ऐसी समस्या चुनना चाहिए जो AC⁰ में स्पष्ट रूप से होती है और सभी बिट पर निर्भर करती है (उदाहरण के लिए, OR फ़ंक्शन का विचार करें)। AC⁰ ⊊ TC⁰ की सख्त अवधारणा उनके कारण होती है कि पॅरिटी और मेज़ॉरिटी (जो दोनों TC⁰ में हैं) को AC⁰ में नहीं माना गया था ^।

उपरोक्त नियंत्रणों के तत्काल परिणाम के रूप में, हमारे पास NC = AC = TC है।

संदर्भ

• Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 3-540-64310-9.