Class Description

mTC0: Monotone TC0

The class of decision problems solvable by a family of monotone TC0 circuits (i.e. constant-depth, polynomial-size, AND, OR, and threshold gates, but no NOT gates).

A uniformity condition could also be imposed.

Defined in [GS90].

Strictly contained in mNC1 [Yao89].

Linked From

mNC1: Monotone NC1

The class of decision problems solvable by a family of monotone NC1 circuits (i.e. AND and OR gates only).

A uniformity condition could also be imposed.

Defined in [GS90].

Strictly contained in mNL [KW88], and indeed in mL [GS91].

Strictly contains mTC0 [Yao89].

More about...