Class Description

PBP: Polynomial-Size Branching Program

Same as k-PBP but with no width restriction.

Equals L/poly [Cob66].

Contains P-OBDD, BPd(P).

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


L/poly: Nonuniform Logarithmic Space

Has the same relation to L as P/poly does to P.

Equals PBP [Cob66].

Contains SL [AKL+79].

More about...


k-PBP: Polynomial-Size Width-k Branching Program

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

More about...


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.

More about...