×

Lower bounds on the complexity of 1-time only branching programs. (English) Zbl 0575.68064

Fundamentals of computation theory, Proc. 5th Int. Conf., Cottbus/Ger. 1985, Lect. Notes Comput. Sci. 199, 90-99 (1985).
[For the entire collection see Zbl 0568.00020.]
A branching program (BP) is a directed acyclic graph where each node has out-degree 2 or zero. Nodes with out-degree equal to zero and called sinks and are labelled with boolean constants. The remaining nodes are labelled with boolean variables taken from a set \(X=\{x_ 1,...,x_ n\}\). There is a distinguished node, called the root which has in-degree equal to zero. A BP computes an n-argument boolean function f as follows: Starting at the root, the value of the variable labelling the current node is tested, if it is zero (one) the next node tested is the left (resp. right) descendant of the current node. The BP computes f if and only if \(\forall \alpha \in \{0,1\}^ n\) the path traced from the root under \(\alpha\) halts at a sink labelled f(\(\alpha)\). The natural complexity measure for a branching program is the number of non-sink nodes. Branching programs are one example of the many forms of restricted boolean networks introduced in attempts to account for the complexity of realising specific boolean functions.
In order to acquire insight about arbitrary branching programs, a number of restricted models have been considered. Among these is the ”1-time only” model \((BP_ 1)\). This imposes the constraint that on any path from the root to a sink each variable is tested at most once. Thus a \(BP_ 1\) has depth at most n. I. Wegener [On the complexity of branching programs and decision trees for clique functions (Univ. Frankfurt, 1984)] proved exponential lower bounds on the \(BP_ 1\)- complexity of certain clique functions. In this paper we show how the argument used may be generalised to yield lower bounds on arbitrary boolean functions. In the remainder of the paper we apply this result to obtain exponential lower bounds on the \(BP_ 1\)-complexity of the directed and undirected Hamiltonian circuit functions and perfect matchings. The lower bounds obtained for the perfect matching and undirected hamiltonian circuit predicates are, to date, to largest established for explicitly defined functions in the model.

MSC:

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
05C45 Eulerian and Hamiltonian graphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Citations:

Zbl 0568.00020