Class Description

TC¹: Log-depth Threshold Circuits

See TC for definition.

In addition to the different gatesets allowed in place of AND, OR, THR, also equivalent to arithmetic/counting analogue of AC¹ modulo p_n (the nth prime) [RT92].

Linked From

CL: Catalytic Logspace

The class CSPACE with work space ${\displaystyle O(\log n)}$ and catalytic space ${\displaystyle n^{O(1)}}$.

Contains TC¹ and is contained in ZPP [BCKLS14].

Defined in [BCKLS14].

More about...