Class Description

PAC⁰: Probabilistic AC⁰

The Political Action Committee for computational complexity research.

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

Equals TC⁰ and C₌AC⁰ under logspace uniformity [ABL98].

Linked From

C₌AC⁰: Exact-Counting AC⁰

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

Equals TC⁰ and PAC⁰ under logspace uniformity [ABL98].

More about...