Branching programs give us a nice way to model time and space bounds
for Boolean functions in a simple non-uniform model. A branching
program is a directed acyclic graph where every non-leaf node is
labeled by a variable and has two edges labeled One and Zero. All of
the leaves are labeled Accept or Reject. Given an input, one follows
a path taking the One edge on a node labeled *i* if the *i*th
input bit is one and the Zero edge otherwise.

The depth (length of the longest path) of the branching program represents time and log of the size represents space. Lower bounds on branching programs give us lower bounds on unrestricted computation.

In 1999, Miklós Ajtai gave the first polynomial-time computable Boolean function for which any subexponential-size deterministic branching program requires superlinear length.

Ajtai creates a function based on quadratic forms and builds on techniques used in his slightly earlier paper.

For more details I recommend the paper Time-space tradeoff lower bounds for randomized computation of decision problems by Beame, Saks, Sun and Vee which gives a nice history of the problem and the techniques to solve it and generalizes Ajtai's work to the probabilistic setting.

## No comments:

## Post a Comment