A branching program is a directed acyclic graph with a designated start vertex. Each (non-sink) vertex is labeled by the name of an input bit, and has two outgoing edges, one of which is followed if that input bit is 0, the other if the bit is 1. A sink vertex can be either an 'accept' or a 'reject' vertex.
The size of the branching program is the number of vertices. The branching program has width k if the vertices can be sorted into levels, each with at most k vertices, such that each edge goes from a level to the one immediately after it.
Then k-PBP is the class of decision problems solvable by a family of polynomial-size, width-k branching programs. (A uniformity condition may also be imposed.)
k-PBP equals (nonuniform) NC1 for constant k at least 5 [Bar89]. On the other hand, 4-PBP is in ACC0 [BT88].
Contained in k-EQBP, as well as PBP.
See also BPd(P).
Same as AC0[m], but now the constant-depth circuit can contain MOD m gates for any m.
Contained in TC0.
Indeed, can be simulated by depth-3 threshold circuits of quasipolynomial size [Yao90].
According to [All96], there is no good evidence for the existence of cryptographically secure functions in ACC0.
There is no non-uniform ACC0 circuits of polynomial size for NTIMES[2n] and no ACC0 circuit of size 2nO(1) for ENP (The class E with an NP oracle). These are the only two known nontrivial lower bounds against ACC0 and were recently discovered by [Wil11].
Defined in [Weg88].
The class of decision problems solvable by a family of polynomial size branching programs, with the additional condition that each bit of the input is tested at most d times.
BPd(P) strictly contains BPd-1(P), for every d > 1 [Tha98].
Contained in PBP.
Alternate name for k-PBP.
See k-PBP for the definition of a classical branching program.
A quantum branching program is the natural quantum generalization: we have a quantum state in a Hilbert space of dimension k. Each step t consists of applying a unitary matrix U(t)(xi): that is, U(t) depends on a single bit xi of the input. (So these are the quantum analogues of so-called oblivious branching programs.) In the end we measure to decide whether to accept; there must be zero probability of error.
Defined in [AMP02], where it was also shown that NC1 is contained in 2-EQBP.
k-BQBP can be defined similarly.
See NC for definition.
[KV94] give a family of functions that is computable in NC1, but not efficiently learnable unless there exists an efficient algorithm for factoring Blum integers.
Was shown to equal 5-PBP [Bar89]. On the other hand, width 5 is necessary unless NC1 = ACC0 [BT88].
As an application of this result, NC1 can be simulated on a quantum computer with three qubits, one initialized to a pure state and the remaining two in the maximally mixed state [ASV00]. Surprisingly, [AMP02] showed that only a single qubit is needed to simulate NC1 - i.e. that NC1 is contained in 2-EQBP. (Complex amplitudes are needed for this result.)
Contains TC0.
NC1 contains the integer division problem [BCH86], even if an L-uniformity condition is imposed [CDL01].
UE*-uniform NC1 is equal to ALOGTIME [RUZ81].
Same as k-PBP but with no width restriction.
An ordered binary decision diagram (OBDD) is a branching program (see k-PBP), with the additional constraint that if xi is queried before xj on any path, then i<j.
Then P-OBDD is the class of decision problems solvable by polynomial-size OBDD's.
Contained in PBP, as well as BPP-OBDD.