Class Description

PBP: Polynomial-Size Branching Program

Same as k-PBP but with no width restriction.

Linked From

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.

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

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 x_i is queried before x_j 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.