Class Description

C=AC0: Exact-Counting AC0

The class of problems for which there exists a DiffAC0 function f such that the answer is "yes" on input x if and only if f(x)=0.

Equals TC0 and PAC0 under logspace uniformity [ABL98].

Linked From

PAC0: Probabilistic AC0

The Political Action Committee for computational complexity research.

The class of problems for which there exists a DiffAC0 function f such that the answer is "yes" on input x if and only if f(x)>0.

Equals TC0 and C=AC0 under logspace uniformity [ABL98].

More about...