Class Description

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

BP_d(P) strictly contains BP_d-1(P), for every d > 1 [Tha98].

Contained in PBP.

See also: P-OBDD, k-PBP.

Linked From

PBP: Polynomial-Size Branching Program

Same as k-PBP but with no width restriction.

Equals L/poly [Cob66].

Contains P-OBDD, BP_d(P).

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) NC¹ for constant k at least 5 [Bar89]. On the other hand, 4-PBP is in ACC⁰ [BT88].

Contained in k-EQBP, as well as PBP.

See also BP_d(P).

More about...