Class Description

βFOLL: Limited-Nondeterminism FOLL

β_kFOLL is the class of decision problems solvable by a uniform family of polynomial-sized FOLL circuits that accept O(log^k 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(log^k 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 β₂FOLL 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 AC⁰-computable reduction from Graph Isomorphism to Quasigroup Isomorphism.

Linked From

No class.