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.
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.
Same as P-OBDD, except that probabilistic transitions are allowed and the OBDD need only accept with probability at least 2/3.
Does not contain the integer multiplication problem [AK96].
Strictly contained in BQP-OBDD [NHK00].
Same as P-OBDD, except that unitary (quantum) transitions are allowed and the OBDD need only accept with probability at least 2/3.
Strictly contains BPP-OBDD [NHK00].
Same as k-PBP but with no width restriction.