Conferences in Research and Practice in Information Technology
  

Online Version - Last Updated - 20 Jan 2012

 

 
Home
 

 
Procedures and Resources for Authors

 
Information and Resources for Volume Editors
 

 
Orders and Subscriptions
 

 
Published Articles

 
Upcoming Volumes
 

 
Contact Us
 

 
Useful External Links
 

 
CRPIT Site Search
 
    

Complexity of Counting Output Patterns of Logic Circuits

Uchizawa, K., Wang, Z., Morizumi, H. and Zhou, X.

    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
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS