β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.
No class.