A Non-linear Time Lower Bound for Boolean Branching Programs

We prove that for all positive integer k and for all sufficiently small /spl epsiv/>0 if n is sufficiently large then there is no Boolean (or 2-way) branching program of size less than 2/sup em/ which for all inputs X/spl sube/{0, 1, .. ., n-1} computes in time kn the parity of the number of elements of the set of all pairs (x, y) with the property x/spl isin/X, y/spl isin/X, x 0 is an absolute constant and n is sufficiently large with respect to /spl delta/.

Authors

• Miklós Ajtai

Keywords

• Binary decision diagrams
• Time measurement
• Size measurement
• Input variables
• Performance evaluation
• Registers
• Content addressable storage
• Branching Program
• Uniform Distribution
• Computation Time
• Sufficiently Large
• Proof Of Theorem
• Positive Integer
• Elements
• Nodes In The Graph
• Linear Time
• Submatrix
• Random Matrix
• Linear Graph
• Program Length
• Outgoing Edges
• Program Size
• Input Bits
• Absolute Constant
• Values Of Variables
• Set Of Functions
• Cardinality
• Part Of The Input
• N-dimensional Vector
• Directed Acyclic Graph