Class Description

DiffAC0: Difference #AC0

The class of functions from {0,1}n to integers expressible as the difference of two #AC0 functions.

Equals GapAC0 under logspace uniformity [ABL98].

Linked From

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].

More about...


GapAC0: Gap #AC0

The class of functions from {0,1}n to integers computable by constant-depth, polynomial-size arithmetic circuits with addition and multiplication gates and the constants 0, 1, and -1. (The only difference from #AC0 is the ability to subtract, using the constant -1.)

Equals DiffAC0 under logspace uniformity [ABL98].

More about...


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...