2
$\begingroup$

$FOLL$ or $FO (\log \log n)$ is a complexity class of all problems solvable by uniform poly-size circuit families of unbounded fan-in and depth $O(\log \log n)$.

$AC^2$ is a complexity class of all problems recognized by boolean circuits with depth $O(\log ^{2}n)$ and polynomial number of unlimited fan in AND and OR gate.

Question. : What is a difference between $FOLL$ and $AC^2$?

In the definition of $FOLL$ they have used "uniform " poly-size and in the definition of $AC^2$ they are saying boolean circuits.

$\endgroup$
3
$\begingroup$

The functions $\log \log n$ and $\log^2 n = (\log n)^2$ are quite different. The latter grows much faster than the former: $\log \log n = o(\log^2 n)$. This shows that FOLL is a subset of AC2 (and even of the smaller class AC1).

Uniformity is a different aspect in which the two classes differ: FOLL is a class of uniform circuits, whereas the AC hierarchy captures non-uniform circuits. As such, even AC0 circuits can compute uncomputable functions, something that FOLL cannot do.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.