LCS Publication Details
Publication Title: WIDTH-3 PERMUTATION BRANCHING PROGRAMS
Publication Author: Barrington, David A.
Additional Authors:
LCS Document Number: MIT-LCS-TM-293
Publication Date: 12-1-1985
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
We consider a restricted class of width-3 branching programs where each column of nodes depends on a single variable, and the O-edges and 1-edges out of each column form a permutation. In this model, parity and mod-3 function are easy to calculate, but the and-function is hard. We show that any function of n inputs can be calculated in length 0(2n), and that the and-function in particular requires length 0(2n) if the branching program has one accept node and one reject node.
To obtain this publication:

    To purchase a printed copy of this publication please contact MIT Document Services.