Universal circuits (Preliminary Report)

Abstract

We show that there is a combinational (acyclic) Boolean circuit of complexity 0(slog s), that can be made to compute any Boolean function of complexity s by setting its specially designated set of control inputs to appropriate fixed values. We investigate the construction of such “universal circuits” further so as to exhibit directions in which refinements of the asymptotic multiplicative constant factor in the complexity bound can be found. In this pursuit useful detailed guidance is provided by available lower bound arguments. In the final section we discuss some other problems in computational complexity that can be related directly to the graph-theoretic ideas behind our constructions. For motivation we start by illustrating some of the applications of universal circuits themselves.