Let C be a logic circuit consisting of s gates g1, g2, . . . , gs, then the output pattern of C for an input x {0, 1}n is defined to be a vector (g1(x), g2(x), . . . , gs(x)) {0, 1}s of the outputs of
g1, g2, . . . , gs for x. For each f : {0, 1}2 {0, 1}, we define an f-circuit as a logic circuit where every gate computes f, and investigate computational complexity of the following counting problem: Given an f-circuit C, how many output patterns arise in C? We then provide a dichotomy result on the counting problem: We prove that the problem is solvable in polynomial time if f is PARITY or any degenerate function, while the problem is #P-complete even for constant-depth f-circuits if f is one of the other functions, such as AND, OR, NAND and NOR.
|
| Cite as: Uchizawa, K., Wang, Z., Morizumi, H. and Zhou, X. (2013). Complexity of Counting Output Patterns of Logic Circuits. In Proc. Theory of Computing 2013 (CATS 2013) Adelaide, Australia. CRPIT, 141. Wirth, A. Eds., ACS. 37-43 |
(from crpit.com)
