Class Description

βMAC⁰: Limited-Nondeterminism MAC⁰

β_kMAC⁰ is the class of decision problems solvable by a uniform family of polynomial-sized MAC⁰ circuits that accept O(log^k n) nondeterministic input bits, with the same acceptance mechanism as MAC⁰.

βMAC⁰ is the union of β_kMAC⁰ over all constant k.

For any constant k, β_kMAC⁰ is contained in β_kTC⁰. In particular, β₁MAC⁰ is contained in β₁TC⁰ = TC⁰.

We note that β_kMAC⁰ = NMAC⁰(log^k n).

The notion of a non-deterministic NC circuit was introduced in [Wol94]; see NNC(f(n)).

Linked From

No class.