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].
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.