Class Description

P-OBDD: Polynomial-Size Ordered Binary Decision Diagram

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.

Linked From

BPd(P): Polynomial Size d-Times-Only Branching Program

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.

See also: P-OBDD, k-PBP.

More about...


BPP-OBDD: Polynomial-Size Bounded-Error Ordered Binary Decision Diagram

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

More about...


BQP-OBDD: Polynomial-Size Bounded-Error Quantum Ordered Binary Decision Diagram

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

More about...


PBP: Polynomial-Size Branching Program

Same as k-PBP but with no width restriction.

Equals L/poly [Cob66].

Contains P-OBDD, BPd(P).

More about...