The class of decision problems solvable by a uniform family of polynomial-size, unbounded-fanin, depth O(log log n) circuits with AND, OR, and NOT gates. Equals FO(log log n).
Defined in [BKL+00], where it was also shown that many problems on finite groups are in FOLL.
Contains uniform AC0, and is contained in uniform AC1.
Is not known to be comparable to L or NL.
βkFOLL is the class of decision problems solvable by a uniform family of polynomial-sized FOLL circuits that accept O(logk n) nondeterministic input bits, with the same acceptance mechanism as FOLL.
βFOLL is the union of βkFOLL over all constant k.
We note that βkFOLL = NFOLL(logk n).
The notion of a non-deterministic NC circuit was introduced in [Wol94]; see NNC(f(n)).
Chattopadhyay, Torán, and Wagner [CTW13] showed that β2FOLL contains Quasigroup Isomorphism when the inputs are given by their multiplication tables. Additionally, Chattopadhyay, Torán, and Wagner [CTW13] showed that βkFO((log log n)c) cannot compute Parity for any constants c and k. As a consequence, this rules out many-to-one AC0-computable reduction from Graph Isomorphism to Quasigroup Isomorphism.
The class of decision problems that are reducible to FOLL languages under TC0-computable Turing reductions.
For an Abelian group G and an arbitrary group H given by their multiplication tables, deciding whether G and H are isomorphic belongs to TC0(FOLL). [CTW13].