THE COMPLEXITY OF WORD CIRCUITS

摘要

A word circuit [1] is a directed acyclic graph in which each edge holds a w-bit word (i.e., some x ∈ {0,1}~ω) and each node is a gate computing some binary function g : {0, 1}~ω x{0, 1}~ω→ {0, 1}~ω. The following problem was studied in [1]: How many binary gates are needed to compute a ternary function f : ({0, 1}~ω)~3 → {0,1}~ω. They proved that (2 + 0(1))2" binary gates are enough for any ternary function, and there exists a ternary function which requires word circuits of size (1-o(1))2~ω. One of the open problems in [1] is to gef these bounds tight within a low order term. In this paper we solved this problem by constructing new word circuits for ternary functions of size (1-o(1))2~ω. We investigate the problem in a general setting: How many k-input word gates are needed for computing an n-input word function f : ({0, i}~ω)~n → {0, 1}~ω (here n ≥ k). We show that for any fixed n, (1-0(1))2~((n-k))~ω basic gates are necessary and (1 + o(1))2~((n-k))~ω gates are sufficient (assume w is sufficiently large). Since word circuit is a natural generalization of boolean circuit, we also consider the case when w is a constant and the number of inputs n is sufficiently large. We show that (1 ± o(1))2~(ωn)/(k-1)n basic gates are necessary and sufficient in this case.