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

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

${\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⁰ किसी भी फ़ंक्शन की गणना नहीं कर सकता जो सभी इनपुट बिट्स पर निर्भर करता है। इस प्रकार ऐसी समस्या का चयन करना जो एसी में तुच्छ हो⁰ और सभी बिट्स पर निर्भर करता है दो वर्गों को अलग करता है। (उदाहरण के लिए, OR फ़ंक्शन पर विचार करें।) सख्त नियंत्रण एसी⁰ ⊊ टीसी⁰ आता है क्योंकि समता और बहुमत (जो दोनों टीसी में हैं⁰) को AC में नहीं दिखाया गया था ^।

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

संदर्भ

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