TC (složitost) - TC (complexity)

v teoretická informatika a konkrétně teorie výpočetní složitosti a složitost obvodu, TC je třída složitosti z rozhodovací problémy které lze rozpoznat podle prahových obvodů, které jsou Booleovské obvody s A, NEBO, a Většinové brány. Pro každou pevnou i, třída složitosti TCⁱ skládá se ze všech jazyků, které lze rozpoznat pomocí rodiny prahových obvodů hloubky ${ displaystyle O ( log ^ {i} n)}$, polynomiální velikost a neomezený fan-in. Třída TC je definováno prostřednictvím

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

Vztah k NC a AC

Vztah mezi TC, NC a AC hierarchii lze shrnout takto:

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

Zejména to víme

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

První přísné omezení vyplývá ze skutečnosti, že NC⁰ nemůže vypočítat žádnou funkci, která závisí na všech vstupních bitech. Tedy výběr problému, který je triviálně in AC⁰ a záleží na všech bitech odděluje dvě třídy. (Například zvažte funkci OR.) Přísné omezení AC⁰ ⊊ TC⁰ následuje, protože parita a většina (které jsou oba v TC⁰) bylo prokázáno, že nejsou v AC⁰.^[1][2]

Okamžitým důsledkem výše uvedených omezení je NC = AC = TC.

Reference

• Vollmer, Heribert (1999). Úvod do složitosti obvodů. Berlín: Springer. ISBN  3-540-64310-9.