JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]


Journal of Information Science and Engineering, Vol. 17 No. 5, pp. 857-860


A Depth 3 Circuit Lower Bound for the Parity Function


Shi-Chun Tsai 
Information Management Department 
National Chi-Nan University 
Nantou, 545 Taiwan 
E-mail: tsai@csie.ncnu.edu.tw


    We consider small depth boolean circuits with basis {AND, OR, NOT}. We obtain lower bounds for the parity function using a relatively simple method. We prove that for any depth 3 circuit with top fan-in t, computing the n-variable parity function must have at least wires. Similarly, we obtain a lower bound for computing the depth 4 circuits.


Keywords: computational complexity, circuit complexity, boolean function complexity, lower bound, parity

  Retrieve PDF document (JISE_200105_10.pdf)