Class Description

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

Linked From

#AC0: Sharp-AC0

The class of functions from {0,1}n to nonnegative integers computed by polynomial-size constant-depth arithmetic circuits, using addition and multiplication gates and the constants 0 and 1.

Contained in GapAC0.

More about...


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

More about...